14275Re: Modification of PFGW
- Dec 25, 2003I will make a short reply here (even though this might be a little
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
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
--- In firstname.lastname@example.org, Cletus Emmanuel <cemmanu@y...>
> 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 wecan let PFGW evaluate
> ((N-1)/2), coupled with the loop I speak of. I said "a basic forloop" 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
> Also, can you direct me to the Primeform group? How do I become a
> ---Cletus Emmanuelcemmanu@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 >>