Jacobi symbol using Lehmer's algorithm.

[Torbjorn Granlund]

nisse at lysator.liu.se (Niels Möller) writes:

  > New version (the file is getting rather large now) at
  > http://www.lysator.liu.se/~nisse/misc/jacobi.c
  
  And here's a benchmark on shell:
  
  n             old lehmer subquadratic
     10      13.118  0.600        0.577
     30      31.861  0.471        0.467
    100     441.870  0.288        0.288
    300    3310.419  0.180        0.180
   1000   36827.000  0.121        0.099
   3000  300266.000  0.118        0.058
  10000 3564051.000  0.103        0.029
  
  So at 10000 limbs, the Lehmer code beats the old code by 10 times, and
  then the subquadratic algorithm wins a factor 3.4 more.

Very nice, a factor 34!  But Paul got a factor 100.  :-)

So...what is the speedup @ n=100000?

I predict that we'll give around 200x, also since the quadratic code
will start suffering from L1 cache misses.

Clearly your code is faster than Paul's code, since 200 > 100.  :-D

-- 
Torbjörn