Spin: Multiply unsigned 32 bit by usigned 32 bit with unsigned 64 bit result?
Heater.
Posts: 21,230
Anyone know how I can get a 32 bit by 32 bit multiply with 64 bit result in Spin where all numbers are treated as unsigned?
We have "*" which despite Spin being said to deal in signed numbers only gives the correct 32 bit result regardless of sign.
The we have "**" to get the high half of the result, BUT it sign extends it's operands first so that -1 ** 1 comes out as $FFFFFFFF instead of zero for example.
So how to adjust the results of ** to get an unsigned result? In this case I need all 64 bis correct not just a bigger range than 32 bits.
The reason: In my current obsession with long sequence pseudo random random number generators I have been trying to implement George Marsaglia's MWC256 algorithm in Spin. This is a follow on from his KISS32 algorithm with an improved period of about 2 to the power 8222 !!!
Problem in is relies on unsigned and 64 bit arithmetic which is a bit tricky in Spin. Here is the C version:
That 64 bit addition is doable using some post addition fix up aided by the fact that c fits in 32 bits.
The 64 bit multiply has operands that both fit in 32 bits so we only need to get the unsigned 64 bit result right.
Any ideas?
We have "*" which despite Spin being said to deal in signed numbers only gives the correct 32 bit result regardless of sign.
The we have "**" to get the high half of the result, BUT it sign extends it's operands first so that -1 ** 1 comes out as $FFFFFFFF instead of zero for example.
So how to adjust the results of ** to get an unsigned result? In this case I need all 64 bis correct not just a bigger range than 32 bits.
The reason: In my current obsession with long sequence pseudo random random number generators I have been trying to implement George Marsaglia's MWC256 algorithm in Spin. This is a follow on from his KISS32 algorithm with an improved period of about 2 to the power 8222 !!!
Problem in is relies on unsigned and 64 bit arithmetic which is a bit tricky in Spin. Here is the C version:
/* MWC256 from Usenet posting by G. Marsaglia - Period 2^8222 */
static unsigned int Q[256], c=362436;
unsigned int MWC256(void)
{
unsigned long long t;
static unsigned char i = 255;
t = 809430660ULL * Q[++i] + c;
c = t >> 32;
return (Q[i] = t);
}
That 64 bit addition is doable using some post addition fix up aided by the fact that c fits in 32 bits.
The 64 bit multiply has operands that both fit in 32 bits so we only need to get the unsigned 64 bit result right.
Any ideas?
Comments
Blimey. Two hours asking Google to find something like that on the forums and no luck. Think I skipped over umath as it does not advertise that it does what I want.
Thank you.
Phil,
How come you didn't make mult, dadd and other useful routines in umath PUBlic and advertise as such. They must be of use to many others.
Problem: It does not work.
Well something goes wrong after generating 1000 pseudo random numbers and before 10000. The sequence diverges from the C version in there some where.
I'll poke around with it a bit more.
I hope there aren't any bugs in it. It was pretty thoroughly tested, but that was quite awhile ago. If you find one, please post it here.
Thanks,
-Phil
I suspected that was our motive.
I simply made mult and dadd into PUB and added a couple of routines to return producth and productl. Slow but simple.
I'm fishing for bugs just now, it's probably me anyway.
No errors when checked against the C version of the same operations.
Not totally conclusive as I'm just using random inputs but good enough for me.
So something is up with my MWC256 PRNG.
umath's mult and dadd are just fine.
Turns out my bug was not where I was looking for it, as usual.
Not in the PRNG itself but in it's seed set up (the seeds are 256 longs!!).
Not in the Spin version but in the C reference version on my PC.
I'll post this beast of a PRNG when I have cleaned it up a bit. In case any one wants very high quality PRN's with a gigantic period for their long running Monte Carlo bioinformatics simulations on their multi-Propeller super computers:)
-Phil
I don't believe you!
Oh, OK. I'll test the other 2^64 combinations of inputs to mult and dadd just to be sure. Might take a little while. Just wait there till I get back:)