Very fast power system, for a number.

It works by taking the binary logorithm of the number (i'll get the biggest, for extra precision, but any will do), you then multiply it by the other number, before going and going and turning the log back into a real number using a bitshift. (2^x = 1 << x).
I'm pretty sure theres another way to go and turn it back. With better precision.

For pow(x, y) the code is:

int64 number = maxmin(x, y);int32 * num = (int32 *)Number;Return 1 << (binarylog((int64)num[1])) * num[0]);

Its probably not the best code, but its ok.

Does anybody have a better version?
From,
Nice coder

Now this is a square root just for curiosity's sake (unless implemented in hardware, then it'd seriously be nice).

Heres some egsamples.
65535 (2^16) is equal to 255 (2^8) squared.
So, you can find square roots that way.

Now, what will happen if you have a compisite number? like 2^8 + 2^16?

Thats 65791.

or
1000000100000000
Now the square root of 65791 is aproximatly 257 (257*257 is 66049).

Now, by going and getting each bit, and halving it, you could get yourself a square root.

Lets try 2^8 + 2^ 4 thats 272. 272 squared is 73984.

This could probably be used as a good guess for the square root of a number.
It could also be used (with a little refinement) to calculate a really fast square root in hardware (without any very complex circutry).

Some code to get it started:

t = 1;
For (int x = 0;x < n;;) {
sqrt += ((num & t) >> y;
t = t + t;
x++;
sqrt += (num & t) >> y;
t = t + t;
x++;
y++;
}


This should at least be the jist of it.
t is the bitmask, it goes up with the powers of two (to seperate each individual bit). The bit is then shifted down, half way (thus dividing the exponant by two), before being added to sqrt.

This probably doesn't work right, so consider it a first draft.

Actually, i'd try the simpler method:

Sqrt += (num & 2) >> 1;
Sqrt += (num & 4) >> 2;
Sqrt += (num & 8) >> 4;
Sqrt += (num & 16) >> 8;
Sqrt += (num & 32) >> 16;
... //And so on, for the rest of the powers of two.


And it works two!
And it can be computed very well in parellel (making hardware computation easier).

Not sure if it should be sqrt |= or += tho. Any ideas?

From,
Nice coder

Computerised long division

For x / y Where y is smaller then x.Remainder = xshift = sizeof(y);cnum = y << (sizeof(x) - sizof(y));while(1) {	if (cnum > remainder) {	Cnum = Cnum >> Shift; if(!Cnum){break;}	remainder = remainder - cnum;	div++;}Div = Result of the divisionRemainder = Modulus.

This had problems. i'm leaving it here for entertainment value. (see if you can find out what went wrong).

//Simpler versionRemainder = xCnum = ywhile(1) {if (cnum > remainder) {Break;)remainder = remainder - cnum;div++;}

That works, but is very slow.

//A slightly faster (but maybe buggier) one.while(1) {Cnum = Cnum + yif (cnum > remainder) {    x--;    cnum = cnum - y;    break;}x++;}Div = x;Remainder = cnum - remainder;

I'm pretty sure theres a faster one...

Remainder = x;max = [Insert biggest 32 bit number here];min = 1;while(1) {if ((max - min) < 1) {break;}Cdiv = (max + min) >> 1;cnum = y * cdiv;if ((cnum == remainder) {   Break;}if (Cnum > reminder) {   Max = Cdiv;} Else {Min = Cdiv;}}Div = Cdiv;Remainder = Cnum - Remainder; 

Binary search for division. (and modulus at the same time) Nifty?
You just need a fast Multiply routine....

Does anybody have a fast mult routine they want to share?
From,
Nice coder

[Edited by - Nice Coder on January 29, 2005 5:06:46 PM]

Slower/Faster Sqrt method.

lut[32] = {1,2,4,8,16,32,...};

cl = 32for(;cl;) {root = x * x;if (root > n) {   x -= lut[cl];} else {x += lut[cl];}cl--}

Very simlple, but not too fast.

I might put up a fully unrolled one later.

From,
Nice coder

Quote:Original post by sjelkjd

Quote:Original post by Nice Coder
Fast min/max.

if anyone wants to know how each of them work, just ask.

How does this work? Doesn't int b = (x - y) >> 32; underflow to 0?

No,
When x is smaller then y
x - y, will be a negitive number (32 bits long).

We go and we use a signed right shifted, so that if the sign bit is one (like it would be for negitive numbers), the number contains 32 ones. (every bit is one).

on the other hand, if x is greater then y, then it will be a positive number, and the number will be filled with zeros.

We then use the &'s to remove the number we don't want, and to keep the number we want (x & 0) = 0, (x & ~0) = x.

From,
Nice coder

Try x >> 31.

Simple code, for a nice 16bit square root function where hardware multiplication and division are not avalible, and braching is costly. (works well other times, but that is when it really exels).

It needs 512 16bit entries. Meaning that it takes up 1K of ram.

int16 lut[512] = {...}; //malloc and define at the beginning of the procedure,then store a constant pointer reference to it.char * c = (char *)number;int16 output;output |= lut[c];output |= lut[c[1] | 256];

That is fast, and easy to use, for any 16 bit numbers.
It doesn't produce correct square roots, but i'm working on it (its probably going to need a different lut, to the normal (the one that works just like NC's easy square root) one.)
The difference is negligable. from the real sqrt.

From,
Nice coder

Find the lsb of a number.

#define LSB(v)  (v - (v & (v - 1))))

That returns the lsb, (in 2 power form, so for eg. 32, 64, 128, 512, ect. or 0 if v is 0)

One subtraction, one decrement, one and.
Non-parellelisable.

From,
Nice coder