- Dec 25, 2003I will make a short reply here (even though this might be a little

off topic).

1. the primeform group (which supports OpenPFGW at a "user" level)

can be found at http://groups.yahoo.com/group/primeform/

2. Testing for b^((N-1)/2)%N vs b^(N-1)%N saves only 1 squaring.

In you trivial sample below (47) you list that PFGW would loop 46

times. You might want to take a quick refresher on algorithms for

exponentation (Knuth volume 2 is a good reference, as are dozens of

other tomes).

The exponentation used in PFGW (or any math package) only performs a

squaring (with possible multiplication) per each "bit" of the number.

So, testing 3*10^1000000+1 requires only 3321929 "steps", and NOT

10^1000000 steps (there is a HUGE difference between the two).

However, performing the test you have listed (b^((n-1)/2))%n would

require 3321928 steps, thus for a non-trivial change to the code and

logic of the exponentation, you save an extremely trivial amount of

time.

Jim.

--- In primenumbers@yahoogroups.com, Cletus Emmanuel <cemmanu@y...>

wrote:> Mike,

of PFGW, I will admit. However, I am very much willing to learn....

> Let me first say, I am very ignorant when it come to the working

> Yes, I do realize that it is one less iteration. However, if we

can let PFGW evaluate

> ((N-1)/2), coupled with the loop I speak of. I said "a basic for

loop" for two reasons:

>

47 for 2-PRP, based on how this group have explained it to me, it

> 1) because it is (I really think) simple

> 2) My C codes are very rusty and the loop is written in Basic

>

> By no means, am I asking to write Basic codes in PFGW.

>

> Now, let me give an example of this code... if PFGW were to check

would have to check 2^46%47 (which would be 46 iterations) to see if

it equal 1. In the basic loop I speak of, it would take 5 loops

(ofcourse 47 is viewed as a Carol number - a special case). And

that's why I would like for the program to be optimized for

Carol/Kynea numbers.>

member?....

> Also, can you direct me to the Primeform group? How do I become a

> ---Cletus Emmanuel

cemmanu@y... writes:

>

> Mikeoakes2@a... wrote:

> In a message dated 23/12/03 22:00:27 GMT Standard Time,

>

to modify PFGW to check for Carol/Kynea numbers for a while

>

> I've been asking of Chris Nash ( I presume that he is very busy)

now....Can anyone modify PFGW to do b^((N-1)/2)%N rather than b^(N-

1)%N? There is even a faster way (I think) I can let it calculate b^

((N-1)/2)%N (with a basic for loop)....>

example), "to do b^((N-1)/2)%N rather than b^(N-1)%N" takes 999999

>

>

> You do realize, do you, that for N = 2^1000000-1 (for

rather than 1000000 FFTs; in other words, there is a negligible

difference in execution time.>

you think simple ideas involving "a basic for loop" are going to

> PFGW is already a highly optimized and efficient program; so if

make it faster, you are probably mistaken.>

group, or, for implementation issues, openpfgw.

> The proper forum for this discussion is really the primeform

>

> -Mike Oakes

>

>

> ---------------------------------

> Do you Yahoo!?

> Free Pop-Up Blocker - Get it now

>

> [Non-text portions of this message have been removed] - << Previous post in topic Next post in topic >>