Execution time for 32x32 bit multiplication?

Intrepid

What is the worst case execution time for a 32 bit x 32 bit multiplication with a 64 bit result?

Thanks!

rokicki

Here's one algorithm that might have a pretty bad execution time.

1. Generate a random 64-bit result. You can use the ? operator to do this (use it twice; you'll have to use an array or two variables.)

2. Divide that 64-bit value by the first operand. If you have a remainder, go back to 1.

3. Divide that 64-bit value by the second operand. If you have a remainder, go back to 1.

4. Divide the 64-bit value by the first operand *again*. If the result is the same as the second operand, you're probably done. Return the 64-bit value.

5. Go back to 1 and try again.

The runtime here depends on the specific implementation of the random number generator; I suspect for many input values, the runtime may be large.

Intrepid

I should clarify that I would be working in assembly language...

Mike Green

I think you could do this with a 5 instruction loop. At 50ns per instruction (80MHz clock), that would take 8us plus a little to handle setup and signed operands.· If you could afford the memory space to unroll the loop, that could bring it down to a little over 6us.
·

Intrepid

Mike,

Thank you very much, that is exactly what I needed - other than a propeller with hardware multiply/divide!

John

Carl Jacobs

Have a look at JDForth http://forums.parallax.com/showthread.php?p=741699

You might not want to use forth, but the kernel has multiply and divide routines that do 32 bits x 32 bits / 32 bits
with a 64 bit intermediate. The multiply (32 x 32 => 64) and divide (64 / 32 => 32) routines both use
4 instructions per loop.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Carl Jacobs


JDForth - Forth to Spin Compiler http://www.jacobsdesign.com.au/software/jdforth/jdforth.php
Includes: FAT16 support for SD cards. Bit-bash Serial at 2M baud. 32-bit floating point maths.·Fib(28) in 0.86 seconds. ~3x faster than spin, ~40% larger than spin.