mersenneforum.org  

Go Back   mersenneforum.org > Search Forums

Showing results 1 to 25 of 31
Search took 0.01 seconds.
Search: Posts Made By: SPWorley
Forum: Hardware 2009-09-07, 21:15
Replies: 142
Views: 13,047
Posted By SPWorley
Exactly, it's 8 SP : 1 DP : 1 SF for the G200...

Exactly, it's 8 SP : 1 DP : 1 SF for the G200 Nvidia cards. The ATI isn't a constant 5x at all.. it's variable based on operation type since it's software, but also it's not IEEE either so sometimes...
Forum: Hardware 2009-09-07, 18:31
Replies: 142
Views: 13,047
Posted By SPWorley
The AMD and NVidia approaches are very different....

The AMD and NVidia approaches are very different.

AMD uses its single-precision ALUs with microcode programming to produce DP results. These are not IEEE doubles, though, but still much higher...
Forum: Math 2009-08-28, 17:18
Replies: 6
Views: 637
Posted By SPWorley
Kevin, wow, thanks very much. This is not an...

Kevin, wow, thanks very much. This is not an answer I expected... my amateur gut feeling was leading me in a very wrong direction.
Thanks for the fast and expert answer. Now I have yet a new...
Forum: Math 2009-08-28, 06:06
Replies: 6
Views: 637
Posted By SPWorley
Number and identity of n-th roots of 1 mod p

How can you count (and/or compute) the solutions for the relationship

a^n ==1 mod p

where p is prime, n is fixed?

Obviously for some n, the answer is easy. If n=2, this is the square root,...
Forum: Math 2009-08-26, 03:05
Replies: 3
Views: 580
Posted By SPWorley
Thanks very much for the references.. it's all...

Thanks very much for the references.. it's all there in Crandall/Pomerance.

Pretty straightforward, too!

I appreciate it.
Forum: Math 2009-08-25, 07:32
Replies: 3
Views: 580
Posted By SPWorley
Breaking a prime p into a^2 + 3* b^2

I'm playing with cubic reciprocity (http://en.wikipedia.org/wiki/Cubic_reciprocity) formulas.

From that link, it states "A theorem of Fermat states that every prime p ≡ 1 (mod 3) is the sum of a...
Forum: Math 2009-08-24, 23:26
Replies: 8
Views: 1,642
Posted By SPWorley
Well the fun part is that I'm doing this on a new...

Well the fun part is that I'm doing this on a new architecture: a GPU! And there's arguments to use a 24 bit word size.. there's hardware support for using the FPU to do integer math with 24 bit...
Forum: Math 2009-08-24, 23:22
Replies: 8
Views: 1,642
Posted By SPWorley
Thanks much for the authoritative answer! I did...

Thanks much for the authoritative answer!
I did notice the (many!) multiple methods defined, especially for the low bit ranges of < 2^64. I guess in the days of 486 processors, it was a struggle...
Forum: Math 2009-08-24, 20:34
Replies: 8
Views: 1,642
Posted By SPWorley
I bet you're right.. that's exactly what I was...

I bet you're right.. that's exactly what I was thinking of when I called it "classic division and subtraction".

But that's also noticably slower (in my own code) than doing it with Montgomery...
Forum: Math 2009-08-24, 20:06
Replies: 8
Views: 1,642
Posted By SPWorley
Yes, indeed, but that does not describe the...

Yes, indeed, but that does not describe the strategy P95 is using for its mod-square computation used in the loop to find 2^p mod q.
Forum: Math 2009-08-24, 17:56
Replies: 8
Views: 1,642
Posted By SPWorley
P95 trial division strategy

I'm experimenting with my own GPU Mersenne trial division tool.. it's got its own fun challenges.

The classic way to test for divisibility of 2^p -1 by q is to compute
2^p mod q and look for a...
Forum: Math 2009-08-22, 07:12
Replies: 5
Views: 679
Posted By SPWorley
Yes, it's pretty clear that "its" are more than...

Yes, it's pretty clear that "its" are more than one test. But it's unclear how many, or if it really has any meaning.

Prime95 doesn't give any stats about the number of values it's tested.
I...
Forum: Math 2009-08-21, 17:12
Replies: 5
Views: 679
Posted By SPWorley
Mersenne trial division candidate counts

Another thread mentioned the nice benchmark page (http://mersenne-aries.sili.net/throughput.php?cpu=Intel%28R%29+Atom%28TM%29+CPU+330+%40+1.60GHz%7C512%7C0&mhz=1600) listing hardware speeds for FFT...
Forum: Math 2009-08-20, 22:06
Replies: 25
Views: 1,277
Posted By SPWorley
Now that is a nearly ideal link to start...

Now that is a nearly ideal link to start exploring. I'm not sure why I didn't find it when I was searching myself.

I agree.. there's a lot of discussion there! And maybe a decent algorithm or two,...
Forum: Math 2009-08-20, 22:02
Replies: 25
Views: 1,277
Posted By SPWorley
It is compared to the Legendre computation. That...

It is compared to the Legendre computation. That takes roughly log2(p)/4 mod p computes of values ~=p. The general exponentiation needs roughly 3/2 * log2(p) mod p computes of values ~= p^2, not...
Forum: Math 2009-08-20, 21:41
Replies: 25
Views: 1,277
Posted By SPWorley
Thanks for the quick reply! This is useful,...

Thanks for the quick reply!

This is useful, since it provides a clear general algorithm for evaluating the answer.

The annoying part is that for large p, computing x^(large) mod p is...
Forum: Math 2009-08-20, 21:18
Replies: 25
Views: 1,277
Posted By SPWorley
Residue identification algorithm

I'm trying to understand the identification of residues of x^n mod p, where p is an odd prime.

For the residues of x^2 mod p, there are exactly (p+1)/2 residues. You can compute whether a specific...
Forum: Math 2009-08-17, 17:41
Replies: 5
Views: 1,431
Posted By SPWorley
A followup question on Montgomery reduction. ...

A followup question on Montgomery reduction.

Using a radix R=2^s is most common of course.
But the Montgomery method only works with N that are coprime to R..
so for the R=2^s case, N must be...
Forum: Math 2009-08-17, 04:43
Replies: 5
Views: 1,431
Posted By SPWorley
Thanks for the verification! But that...

Thanks for the verification!

But that laddering code is awkward. It doesn't match the 9.3.1 code, it unwraps one extra pass for the high bit, which makes it uselessly compute a full and...
Forum: Math 2009-08-17, 00:34
Replies: 5
Views: 1,431
Posted By SPWorley
Montgomery method in Prime Numbers: ACP

I love the book Prime Numbers: a Computational Perspective. (http://www.amazon.com/Prime-Numbers-Computational-Richard-Crandall/dp/0387252827)
But I'm going wild trying to get Montgomery reduction...
Forum: Lounge 2009-07-28, 03:44
Replies: 20
Views: 1,144
Posted By SPWorley
Too appropriate not to post...

Too appropriate not to post...
Forum: Lounge 2009-07-28, 03:41
Replies: 20
Views: 1,144
Posted By SPWorley
He seemed quite happy to get some notes I sent...

He seemed quite happy to get some notes I sent him a few years back. Anyone mailing him went through some effort, so he's usually interested.

His astounding encyclopediac knowledge was proved yet...
Forum: Programming 2009-07-26, 00:06
Replies: 10
Views: 2,339
Posted By SPWorley
Alex, wow, excellent.. I would never have found...

Alex, wow, excellent.. I would never have found that. This is also a lot to digest! Thanks.

Knuth was so correct when he wrote that there was a rich and mysterious theory behind efficient addition...
Forum: Programming 2009-07-25, 14:57
Replies: 10
Views: 2,339
Posted By SPWorley
Googling for Montgomery PRAC doesn't turn up...

Googling for Montgomery PRAC doesn't turn up anything.
Is this the idea of precomputing a table of 1 x^2 x^3 x^4 x^5 x^6 x^7
(or up to some 2^m -1) and then taking big steps of m bits at once and...
Forum: Programming 2009-07-25, 14:53
Replies: 10
Views: 2,339
Posted By SPWorley
Excellent, lots of useful details in there!

Excellent, lots of useful details in there!
Showing results 1 to 25 of 31

 
All times are UTC. The time now is 09:40.

Fri Nov 27 09:40:41 UTC 2020 up 78 days, 6:51, 4 users, load averages: 1.04, 1.01, 1.06

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.