TR Forums

Because of the way it was written advertising a £5.19 pot of paint, I was trying to do 5^19 today in my head. I summarised that the easiest wayI could find to do this on paper would be as follows:



Done using the pow function in C, that would only require 9 multiplications and a divide by 5, as opposed to 19 multiplications to get the figure originally. Obviously, this isn't a great speed up, but with larger exponents it could be. And at the end of the day, this was just a bit of fun to me.

If a number is prime, you just raise to the next non-prime exponent (add one ) and remember to divide by five at the end...

Are there any quick ways to find two numbers that will come reasonably close (+ or - a few) to the desired exponent?

Maybe some kind of LCM method would be good, but then you're adding divisions and arrays and things...
-Mole

{first 10-digit prime found in consecutive digits of e}.com

-what website am i?

(i know answer is on the internet, so show me the work how you got the answer!)

IntelMole wrote:

Done using the pow function in C, that would only require 9 multiplications and a divide by 5, as opposed to 19 multiplications to get the figure originally.

Except divides are relatively expensive (if possible you multiply by 1/x instead), and there are better ways to go than 19 multiplications anyway. Modern fp units have lookups to make logs and exps cheap; even the x87 has several instructions for that.

IntelMole wrote:

Done using the pow function in C, that would only require 9 multiplications and a divide by 5, as opposed to 19 multiplications to get the figure originally. Obviously, this isn't a great speed up, but with larger exponents it could be. And at the end of the day, this was just a bit of fun to me.

You can also do it as 19 shifts and 19 adds, significantly faster than 19 multiplies. Probably not as quick as dumping it to an FP unit, but when talking about stuff like this, one has to realize there are a lot a processors floating around that don't have FP units.

--SS

IntelMole wrote:

If a number is prime, you just raise to the next non-prime exponent (add one ) and remember to divide by five at the end...

It would take longer to work out if any given number is prime than to actually just do the multiplications probally.

So I assume you never timed it to see if it was actually faster. Not exactly the best way to do speed optimizations.

SecretSquirrel nailed it precisely. If you know the number you're multiplying by beforehand, you can take the multiplication operations and separate them into left-shifts and adds. Likewise, you can take division operations and separate them into right-shifts and divisions.

AMM wrote:

IntelMole wrote:

If a number is prime, you just raise to the next non-prime exponent (add one ) and remember to divide by five at the end...

It would take longer to work out if any given number is prime than to actually just do the multiplications probally.

I realised that too on the way home

Answer is to forget about prime numbers, and just mod 2 the sucker.
-Mole