On Nov 10, 2007 11:53 AM, Steffen <[EMAIL PROTECTED]> wrote:
> Original:
> Time: CPU 9.94 s, Wall: 10.09 s
> Number of roots found:
> 0
> Tonelli:
> Time: CPU 0.00 s, Wall: 0.00 s
> Number of roots found:
> 0
Wow, that's an improvement!
I've made this trac #1138
http://trac.sagemath.org/sage
Hi,
> Could you post some cool impressive benchmarks? :-)
>
> william
ok :-)
Here the result for finding one root in GF(p) where p is 128, 256 and
512 bit prime:
Results for 128 bit prime:
Original:
Time: CPU 0.04 s, Wall: 0.04 s
Number of roots found:
1
Tonelli:
Time: CPU 0.00 s, Wall: 0.00
On Nov 9, 2007 11:19 PM, Steffen <[EMAIL PROTECTED]> wrote:
> Hi, I have implemented the Tonelli and Shanks algorithm which has a
> complexity of O(ln^4(p)) and appears to be amazing fast. So far its a
Could you post some cool impressive benchmarks? :-)
william
> quick and dirty implementatio
Hi, I have implemented the Tonelli and Shanks algorithm which has a
complexity of O(ln^4(p)) and appears to be amazing fast. So far its a
quick and dirty implementation directly in my Sage file and without
error handling. I will ask Martin (when meeting him next time in the
office) how to integrat
I see. In my example a was
sage: type(a)
John
On 09/11/2007, Robert Bradshaw <[EMAIL PROTECTED]> wrote:
>
> On Nov 9, 2007, at 1:43 PM, John Cremona wrote:
>
> > [Hello Robert -- are you in Bristol yet?]
>
> Just got in.
>
> > I'm puzzled now. My comment on inefficiency and Steffen's were ba
On Nov 9, 2007, at 1:43 PM, John Cremona wrote:
> [Hello Robert -- are you in Bristol yet?]
Just got in.
> I'm puzzled now. My comment on inefficiency and Steffen's were based
> on the code
>> for i from 0 <= i <= n/2:
>> if (i*i) % n == self.ivalue:
>>
[Hello Robert -- are you in Bristol yet?]
I'm puzzled now. My comment on inefficiency and Steffen's were based
on the code
> for i from 0 <= i <= n/2:
> if (i*i) % n == self.ivalue:
> return self._new_c(i)
>
but now when I do a.sqrt??
On Nov 9, 2007, at 11:46 AM, Steffen wrote:
> The easier %4 == 3 case seems to be implemented efficiently, but the
> %4 == 1 not. The algo from Tonelli and Shanks might be a good solution
> here. Any thoughts on other/better algorithm?
>
> Steffen
I actually wrote this code. It eventually dispat
You are right, that is a really stupid algorithm for p=1 (mod 4)!
I will suggest this as something easy to be fixed at Sage Days 6
(which is just starting). One could either use pari to do the sqrt
more efficiently, or implement something like Tonelli-Shanks as you
suggest.
John
On 09/11/2007,
Thx, I am wondering why I did not try the command a.sqrt?? on my own.
However, it seems as the implemented algorithm is not the most
efficient one. My result from a.sqrt?? from the latest release:
def sqrt(self, extend=True, all=False):
cdef int_fast32_t i, n = self.__modulus.int32
Use the ?? operator to see the algorithm:
sage: a=GF(next_prime(10^6)).random_element()^2;
sage: a.sqrt??
Type: builtin_function_or_method
Base Class:
String Form:
Namespace: Interactive
Source:
def sqrt(self, extend=True, all=False):
r"""
Returns squ
11 matches
Mail list logo
