n*n 1500% times faster than Pow(n,2)?

[DarkDragon]

Hello,

thanks for the answers.

First, as you're using LOGs and floats it's likely you have numbers stored in floating point format. This will be some representation of the number as:

Code: Select all

sign * Mantisssa  * 2^exponent

I would have to convert the java floats to IEEE 754 floats and read the mantissa and exponent from there. It is a long time ago since I did such things.

@Kaeru Gaman:
Not really. With your method I would just get integers as result. I need floating point values.

[Helle]

I think, this is fast:

Code: Select all

;Lg(Z) = (1/Ln(10)*Ln(Z)
;K = 1/Ln(10)
 
#K1=0.434294481903      ;1/Ln(10)
#K2=0.301029995664      ;LOG(2)

Z.f=1850
Z1.f=Z                  ;only for Messagerequester!

While Z>1
  Z=Z/2                 ;shift not possible, float!
  E+1
Wend

A.f=Z-1
B.f=Z+1

AQ.f=A*A
BQ.f=B*B

LN.f=A/B
  
M=7         
For N=3 To M Step 2     ;M for precision (3,5,7,9...)
  A=A*AQ
  B=B*BQ
  LN=LN+(A/(N*B))
Next
LOG.f=2*#K1*LN
LOG=LOG+(E*#K2)

MessageRequester("LOG-Test","LOG : "+StrF(LOG)+#LFCR$+"PB :    "+StrF(Log10(Z1)))

Gruss
Helle

Edit: No shift! Compact. 10.08.2007

[DarkDragon]

I think, this is fast:

Yes, it is! Thanks.

[dioxin]

DarkDragon,
I don't know Java but it is very likely to use the same format for it's floats as everywhere else. It would be silly not to as most hardware follows the same floating point standard.

Even if it doesn't, there's no need for a "conversion" to IEE 754. You just need to extract the bits in the mantissa and exponenet from wherever they happen to be.

http://www.javaworld.com/javaworld/jw-1 ... tml?page=2

And here http://www.math.utah.edu/~beebe/software/ieee/ I found this quote:

The architectural specification of Java requires IEEE 754 arithmetic, but only a subset of it,

So it looks like the same IEEE754 spec is used by Java.




Helle,
That's the same basic algorithm I outlined above and you can speed it up in a number of ways.

By extracting the exponent as I mentioned earlier you save that While Z>1 loop with its slow divide each time. This can take a lot of time especially if the initial number is large and DarkDragon did say he wants it fast for large numbers.
As a half-way step, use Z=Z*0.5 instead of the slower Z=Z/2. For large initial Z you'll notice the time saving.

You can also rearrange the arithmetic inside the FOR N loop to reduce the calculations required each loop to less than half of what you're doing. You can get it down to 2 adds and 1 multiply for each iteration of the FOR loop.

You can even do away with the loop completely since 4 iterations gives sufficient accuracy you can just precalculate a lot of the values and assign them as constants.


The entire code, after the scaling, can be reduced to something like this:

Code: Select all

'define a few constants
onethird=0.33333333
onefifth=0.2
oneseventh=0.14285714

k=0.868588964    '2*LOG10(e) for base conversion

'the numer to get the LOG10 of (we assume it's been scaled to between 0.5 and 1.0)
z=0.7500033


'now the calculation
x=(z-1)/(z+1)

x2=x * x
intermediate= x * x2

    answer= x + intermediate * onethird
    intermediate= intermediate * x2
    answer= answer + intermediate * onefifth
    intermediate= intermediate * x2
    answer= answer + intermediate * oneseventh

    answer=answer * k     'convert to BASE10 and scale by 2 as needed by the formula

Notice that there is only 1 divide, 8 multiplies and 5 add/subtracts to get accuracy of about 5 decimal digits. That's not bad for a LOG10().

Paul.

[DarkDragon]

Thanks.

DarkDragon,
I don't know Java but it is very likely to use the same format for it's floats as everywhere else. It would be silly not to as most hardware follows the same floating point standard.

Even if it doesn't, there's no need for a "conversion" to IEE 754. You just need to extract the bits in the mantissa and exponenet from wherever they happen to be.

http://www.javaworld.com/javaworld/jw-1 ... tml?page=2

And here http://www.math.utah.edu/~beebe/software/ieee/ I found this quote:

The architectural specification of Java requires IEEE 754 arithmetic, but only a subset of it,

So it looks like the same IEEE754 spec is used by Java.




Helle,
That's the same basic algorithm I outlined above and you can speed it up in a number of ways.

By extracting the exponent as I mentioned earlier you save that While Z>1 loop with its slow divide each time. This can take a lot of time especially if the initial number is large and DarkDragon did say he wants it fast for large numbers.
As a half-way step, use Z=Z*0.5 instead of the slower Z=Z/2. For large initial Z you'll notice the time saving.

You can also rearrange the arithmetic inside the FOR N loop to reduce the calculations required each loop to less than half of what you're doing. You can get it down to 2 adds and 1 multiply for each iteration of the FOR loop.

You can even do away with the loop completely since 4 iterations gives sufficient accuracy you can just precalculate a lot of the values and assign them as constants.


The entire code, after the scaling, can be reduced to something like this:

Code: Select all

'define a few constants
onethird=0.33333333
onefifth=0.2
oneseventh=0.14285714

k=0.868588964    '2*LOG10(e) for base conversion

'the numer to get the LOG10 of (we assume it's been scaled to between 0.5 and 1.0)
z=0.7500033


'now the calculation
x=(z-1)/(z+1)

x2=x * x
intermediate= x * x2

    answer= x + intermediate * onethird
    intermediate= intermediate * x2
    answer= answer + intermediate * onefifth
    intermediate= intermediate * x2
    answer= answer + intermediate * oneseventh
    intermediate= intermediate * x2

    answer=answer * k     'convert to BASE10 and scale by 2 as needed by the formula

Notice that there is only 1 divide, 9 multiplies and 5 add/subtracts to get accuracy of about 5 decimal digits. That's not bad for a LOG10().

Paul.

>>Even if it doesn't, there's no need for a "conversion" to IEE 754. You just need to extract the bits in the mantissa and exponenet from wherever they happen to be.

That's what I meant with conversion.

But how would you get the exponent and mantissa out of a float without using pointers? I can't copy the memory of one floating point var to an integer.

I even did the Z*=0.5 already instead of Z/=2 . That's what I always do.

[dioxin]

DarkDragon,
why can't you use pointers? Does Java not have them?

In PB you can use unions which are probably better than pointers in this case. I don't know about Java but from a quick Google it looks like Java supports unions too.

To use then you create a union structure in which the float and a 32 bit integer are located at the same place in memory. You assign the float to that variable and read back the integer which gives you the bit pattern of the float. Then mask off the bits as needed to extract the mantissa and exponent.


Note that I editted the original post while you were replying to remove an unwanted line at the bottom so it's now slightly better and takes one multiply less.

Paul.

[DarkDragon]

DarkDragon,
why can't you use pointers? Does Java not have them?

Java has no pointers and it has no structures (Just complex objects from classes, but I don't think there are unions ). Maybe with DataOutputStream objects on OutputStream objects on ByteArrays.

[dioxin]

DarkDragon,
http://java.sun.com/developer/JDCTechTi ... t1009.html

That certainly suggests to me that unions can be done in Java but I don't do Java so I'll take your word for it.

Another way to approach it would depend on the range of values you need to handle.
If the range is randomly distributed from say 1 to 10,000,000 then, instead of dividing by 2 until the number is small enough you could do some quick checks such as check if it's > 2^20 and if it is then divide by 2^20 and save 19 divides. For randomly distributed data 90% of numbers would be over 10,000,000 so you'd save lots of time that way. e.g.

Code: Select all

if z > 1048576 then     '1048576 = 2^20
    z=z/1048576    'of course, you replace this with the appropriate multiply
    E=E+20
end if

if z > 1024 then                   '1024 = 2^10
    z=z/1024
    E=E+10
end if

if z > 32 then                       '32 = 2^5
    z=z/32
    E=E+5
end if

now use a 32 entry lookup table for the final 5 count rather than looping up to 5 times round a divide by 2 loop.

But this is just speculation as we don't know exactly what your requirements are.

Paul.

[DarkDragon]

DarkDragon,
http://java.sun.com/developer/JDCTechTi ... t1009.html

That certainly suggests to me that unions can be done in Java but I don't do Java so I'll take your word for it.

Another way to approach it would depend on the range of values you need to handle.
If the range is randomly distributed from say 1 to 10,000,000 then, instead of dividing by 2 until the number is small enough you could do some quick checks such as check if it's > 2^20 and if it is then divide by 2^20 and save 19 divides. For randomly distributed data 90% of numbers would be over 10,000,000 so you'd save lots of time that way. e.g.

Code: Select all

if z > 1048576 then     '1048576 = 2^20
    z=z/1048576    'of course, you replace this with the appropriate multiply
    E=E+20
end if

if z > 1024 then                   '1024 = 2^10
    z=z/1024
    E=E+10
end if

if z > 32 then                       '32 = 2^5
    z=z/32
    E=E+5
end if

now use a 32 entry lookup table for the final 5 count rather than looping up to 5 times round a divide by 2 loop.

But this is just speculation as we don't know exactly what your requirements are.

Paul.

Yeah thanks, it works well now.