Jump to content
  • Advertisement
Sign in to follow this  
Matthew Doucette

better frac algorithm than "x-floor(x)"?

This topic is 4724 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Is there better frac (fractional) algorithm for floating point numbers than x-floor(x) (for positive numbers)? I googled gamedev.net and found no relating threads. Floating points have the "int" and "frac" parts store separately, bit-wise speaking, so there could be a fast algorithm to extract the "frac" part without resorting to using the floor() algorithm. I could potentially save a "sub" instruction if there's a solution to this.

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by Matthew Doucette
Is there better frac (fractional) algorithm for floating point numbers than x-floor(x) (for positive numbers)?

I googled gamedev.net and found no relating threads.

Floating points have the "int" and "frac" parts store separately, bit-wise speaking, so there could be a fast algorithm to extract the "frac" part without resorting to using the floor() algorithm. I could potentially save a "sub" instruction if there's a solution to this.

If they're stored separately, then why can't you just do some bitwise math to get the part you want?

If you're talking about straight floats [which you can't use bit trickery on], in C/C++ there appears to be a function called modf in math.h/cmath that does what you're describing. Even if that's not an option, perhaps you can find an implementation of it somewhere you can get ideas from.

CM

Share this post


Link to post
Share on other sites
Quote:
Original post by Conner McCloud
Quote:
Original post by Matthew Doucette
Is there better frac (fractional) algorithm for floating point numbers than x-floor(x) (for positive numbers)?

I googled gamedev.net and found no relating threads.

Floating points have the "int" and "frac" parts store separately, bit-wise speaking, so there could be a fast algorithm to extract the "frac" part without resorting to using the floor() algorithm. I could potentially save a "sub" instruction if there's a solution to this.

If they're stored separately, then why can't you just do some bitwise math to get the part you want?

If you're talking about straight floats [which you can't use bit trickery on], in C/C++ there appears to be a function called modf in math.h/cmath that does what you're describing. Even if that's not an option, perhaps you can find an implementation of it somewhere you can get ideas from.

CM


I was going to resort to doing bitwise math, if no function existed.

modf appears to be exactly what I want, and I am assuming it does the bitwise 'trickery' that I would have eventually done myself. (I will still do speed testing, of course.) Here's a good link:

http://www.cplusplus.com/ref/cmath/modf.html

r++

Share this post


Link to post
Share on other sites
It seems that using x-floor(x) is faster than modf to extract BOTH the frac and int part of a double float:

--------------------------
fractional = modf(x, &integer);
--------------------------

vs.

--------------------------
integer = floor(x);
fractional = x - integer;
--------------------------

(BTW, all vars in these examples are double floats.)

The bottom example is faster; modf was exactly 5.40% slower. Can someone else speed test this? You would think modf would be at least the same speed, if not faster.

Share this post


Link to post
Share on other sites
I just did some more testing on double floats. I tested on 1,000,000 sample bursts for 60 seconds.


"integer = floor(x);
fractional = x - integer"
-------------------------------------------------
10,366,538.5 "samples" per second.


"fractional = modf(x, &integer)"
-------------------------------------------------
7,517,920.3 "samples" per second.


So, modf is 27.48% slower when extracting both the fractional and integer portion of a double float. (Can someone else test this to verify these results?)

Share this post


Link to post
Share on other sites
I repeated the test with a regular 32-bit float:

"integer = floor(x);
fractional = x - integer"
-------------------------------------------------
10,797,014.5 "samples" per second.


"fractional = modf(x, &integer)"
-------------------------------------------------
7,328,615.5 "samples" per second.


So, modf is 32.12% slower when extracting both the fractional and integer portion of a (regular) float, in these 60 second tests anyway. (Again, can someone else test this to verify these results?)

[Edited by - Matthew Doucette on June 14, 2005 2:16:14 PM]

Share this post


Link to post
Share on other sites
I haven't done anything terribly scientific, but I'm seeing the exact opposite results. modf is slightly faster than floor. When measures to account for negative numbers is added into the floor implementation, the difference becomes a bit more pronounced. It was not by any means a proper benchmark, but there you go. Personally, I would just use modf since it does all the grunt work for you. No worrying about sign and infinite values and whatnot.

CM

Share this post


Link to post
Share on other sites
Quote:
Original post by Matthew Doucette
Quote:
Original post by Conner McCloud
Quote:
Original post by Matthew Doucette
Is there better frac (fractional) algorithm for floating point numbers than x-floor(x) (for positive numbers)?

I googled gamedev.net and found no relating threads.

Floating points have the "int" and "frac" parts store separately, bit-wise speaking, so there could be a fast algorithm to extract the "frac" part without resorting to using the floor() algorithm. I could potentially save a "sub" instruction if there's a solution to this.

If they're stored separately, then why can't you just do some bitwise math to get the part you want?

If you're talking about straight floats [which you can't use bit trickery on], in C/C++ there appears to be a function called modf in math.h/cmath that does what you're describing. Even if that's not an option, perhaps you can find an implementation of it somewhere you can get ideas from.

CM


I was going to resort to doing bitwise math, if no function existed.

modf appears to be exactly what I want, and I am assuming it does the bitwise 'trickery' that I would have eventually done myself. (I will still do speed testing, of course.) Here's a good link:

http://www.cplusplus.com/ref/cmath/modf.html

r++


Sorry to hijack this thread (again. I'm a sever thread hijacker) but where did you find that the fract and the int part of a regular float were stored separately? A 32 bit float is made of a bit sign, a mantissa and an exponent. The value is a function of the mantissa and the exponent - and the function is not that easy, unfortunately - and you cannot treat them separately and expect you'll be able to find a fun trick to do the job as easily :)

Regards,

Share this post


Link to post
Share on other sites
Quote:
Original post by Emmanuel Deloget
Sorry to hijack this thread (again. I'm a sever thread hijacker) but where did you find that the fract and the int part of a regular float were stored separately? A 32 bit float is made of a bit sign, a mantissa and an exponent. The value is a function of the mantissa and the exponent - and the function is not that easy, unfortunately - and you cannot treat them separately and expect you'll be able to find a fun trick to do the job as easily :)


I should have explained better. The integer and fractional part of a floating point are not always stored in the same place, bitwise speaking, but they are store "separately", somewhat. You already know this, but let me explain: A certain amount of the bits indicate the integer value, perfectly, and a certain amount of the bits indicate the fractional value. I understand that depending on the exponent there can be zero bits to describe both. With clever bitshifts and bitwise ANDs you could potentially extract them both quickly. I haven't spent any thought on it, yet, so there may be no such optimization that is worthwhile.

(Oh, and do not mind hijacking any of my threads. I really appreciate your input! I would r++ you but I did that a long time ago.)

[Edited by - Matthew Doucette on June 14, 2005 9:05:27 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Conner McCloud
I haven't done anything terribly scientific, but I'm seeing the exact opposite results. modf is slightly faster than floor. When measures to account for negative numbers is added into the floor implementation, the difference becomes a bit more pronounced. It was not by any means a proper benchmark, but there you go. Personally, I would just use modf since it does all the grunt work for you. No worrying about sign and infinite values and whatnot.


Here is my exact test code:

---------------------------------
fractional = modf(x, &integer);
---------------------------------

and

---------------------------------
integer = floor(x);
fractional = x - integer;
---------------------------------

and the results were that modf was slower.

Also, in my case, I am only using positive values. So my "manual" formula (the bottom one; the one without modf) is optimized in the sense that it does not take into account for negative values. Perhaps this is why it is faster than modf.

My testings were fairly accurate, even with the usage of burst samples, to take into account my CPU going faster and slower as various processes chew up more and less CPU resources. I think my results are more accurate than yours, based on your explanation... but your results makes me wonder what is going on... I need more testing from other people now!

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!