• Announcements

Archived

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

speed freak

Recommended Posts

cheez_keeper    134
Is one multiplication and one subtraction faster than one division (not a bit shift)?

snowmoon    122

Share on other sites
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 on other sites
cheez_keeper    134
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 on other sites
c_wraith    122
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 on other sites
cheez_keeper    134
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 on other sites
cheez_keeper    134
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 on other sites
Diodor    517
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 on other sites
c_wraith    122
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.