Lucas-Lehmer Test (Was Classic programming)

[Jerome H. Fine]

 >Mouse wrote:

>>Quite recently, I have a requirement to square very large unsigned
>>integers up to one billion bits [...]
>>
>Are you aware of faster-than-n^2 multiplication algorithms like
>  
>
Actually, when the algorithm is to square a value, the difficulty 
reduces to ONLY
( n^2 + n ) / 2 which is effectively half of the multiply instructions 
required when two
different numbers are multiplied.  Unfortunately, as you point out, that 
still takes
until half way to the heat-death of the universe.

IN  ADDITION, it is the Lucas-Lehmer primality test:
http://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test
that I wish to implement (so I can understand the details along with
being able to enjoy the challenge).  So the series of one billion bit
multiplications must be repeated (one billion - 2) times.

>Karatsuba, Toom-Cook, or Schönhage-Strassen?  If not, you might want to
>  
>
I have already done that for all three:

Karatsuba algorithm - n1.585
https://en.wikipedia.org/wiki/Karatsuba_algorithm

Toom-Cook multiplication - n1.465
https://en.wikipedia.org/wiki/Toom-Cook_multiplication

One aspect of the Toom-3 algorithm that needs to be solved
is the requirement to divide by 3.  There are a number of other
possible Toom-Cook algorithms which divide the initial value
into three or more parts which may also be even faster and might
not require division, but only a shift.

I understand both the Karatsuba and Toom-Cook algorithms
sufficiently to EVENTUALLY implement both at this point.
However, if I use RT-11 under Ersatz-11 as the starting point,
it is highly probable that it will be necessary to use a DLL that
is written in x86 assembler for the actual implementation of
the subroutine to square, subtract two, then take the modulus.
If I can perform each squaring operation in just one second,
it should take only about 5 years to perform the squaring one
billion times.

One possible improvement might be to activate a second DLL
which executes as a 64-bit program which is called by the
32-bit DLL.  Since I expect to have a 64-bit Win7 system
some time this month which I hope to be able to use to run
Ersatz-11 in 32-bit mode, that MIGHT be possible.  Can
anyone who reads this comment on IF it is possible to have
an additional thread spawned by a 32-bit DLL running under
64-bit Win7 which will execute as a 64-bit DLL?  Since
there is a single 32-bit value which needs to be passed to the
64-bit DLL and a single YES / NO result passed back, that
might be a possible solution which might reduce the execution
time by a factor of four.

Schönhage-Strassen algorithm
https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm

Unfortunately, the Schönhage-Strassen algorithm is still beyond
my capability.  However, I hope to master it eventually and
implement the code.

>look into them; if you're working with numbers that large, such things
>can make the difference between "practical" and "might finish before
>the heat-death of the universe if we're lucky"...though, admittedly,
>for just simple squaring it's probably not all _that_ bad.
>
If anyone can comment on my question regarding the
spawning of a 64-bit DLL from a 32-bit DLL running
under a 64-bit Win7, that would be appreciated!!!!!!

Also, a link to information about how to implement the
Schönhage-Strassen algorithm would also be very
much appreciated.

Jerome Fine