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

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

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

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?

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

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