Archived

This topic is now archived and is closed to further replies.

speed freak

This topic is 5980 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Divisions are usually about 3 times slower than multiplications. But the only way to know for sure is look at the compiled assembler and count clock cycles. The numbers also vary for different hardware and somtimes even for different compilers and sometimes even for different compiler settings.

Edited by - Parveen Kaler on July 30, 2001 2:14:50 PM

Share this post


Link to post
Share on other sites
The reason I asked is in the process of screwing with my game to make it faster I may have figured a way to make finding prime numbers faster... if you make a table of the relations between prime numbers as you find them relative to your base prime number (if you check every prime number this would be 3) so for instance the table would say
.6 (3/5)
0.42... (3/7)
0.27... (3/11)
0.23... (3/13)

then you only perform one division operation on the prime (my favorite example is the non-prime 221) with your base prime number (3 in this example)

221/3 approx equals 73 ... always round up to 74

then MULTIPLY this number times the number in the table and subtract this from the wanna-be prime...

.6 * 74 = 44 (round down always) 44 * 5 = 220 != 221
etc...
.23... * 74 = 17 17 * 13 = 221 == 221 (yea!)

this always seems to work but I just realized I asked my question wrong... is 2 multiplications and one subtraction faster than one division? should be the question... sorry

if you cant tell I havn''t slept in days... I think I will go do that for a few hours now... thanks for any responses to this curious question.

Brett Lynnes
cheez_keeper@hotmail.com

Share this post


Link to post
Share on other sites
Hmm... That''s not a very good method to find primes, you know. If you want a large list of relatively small primes, use a Sieve of Eratosthenes algorithm. If you want a small number of large primes, use randomized Rabin-Karp primality testing.

Share this post


Link to post
Share on other sites
If generating a complete list of primes is your goal, the Sieve is the way to go... what I intended this for is testing the primality of a large single number, or small list of numbers... the best way in fact to come up with that table of primes to the natural root of the wanna-be-prime would be to use a Sieve of Eratosthenes. The Sieve starts to loose ground on a brute force is-divisible-by routine when a number is large just because of the memory requred to store the array which must be 2 times the size of the number you are looking for (limiting a PC like mine with about 25Mb free memory to primes under 3.5 million ... I mean 6 digits... how patetic). I have used a Rabin-Karp algorithm for hashing and searching strings... it is a radix sort that runs in O(n + m) best... is this the same one? I have never heard of using any sort of a hash for primality testing... I am very intrigued. Please respond with info on where I can out more if you please.

Brett Lynnes
cheez_keeper@hotmail.com

Share this post


Link to post
Share on other sites
and I realized I was wrong in my question again... maybe I didn''t sleep long enough... the subtraction is the comparison step... which would also need to be perfomed with a division (or modulo division)... so the REAL question is: is 2 multiplications faster than one division?

Share this post


Link to post
Share on other sites
Well, setup a timer (functions QueryPerformanceCounter QueryPerformanceFrequency) and test it yourself. You''re gonna need a lot of testing anyway if you''re after speed

Share this post


Link to post
Share on other sites
Ok, the problem would be I got the name of the algorithm wrong.. It''s not Rabin-Karp, it''s Miller-Rabin.

It''s not a particularly easy algorithm to translate out of the stupid pseudocode in this book, so I''m not going to try.

Share this post


Link to post
Share on other sites
I found it! looks like fun. As for the speed thing, I did setup a timer ran it a couple of million times. They come out with 2 multiplies coming out just behind one division. This is on my PC running Windows, who knows how the processor sharing actually affects this. I ran it as a .asm and as a .cpp with and without optimisations, the result was always the division comig out ahead... later.

Brett Lynnes
cheez_keeper@hotmail.com

Share this post


Link to post
Share on other sites