QB64.org Forum
Active Forums => QB64 Discussion => Topic started by: TerryRitchie on September 22, 2018, 10:57:25 pm
-
When I run the test code below provided by Steve I get:
1.539 seconds for Hypot
1.367 seconds for Math stuff
_HYPOT should be faster, correct?
This is curious, change the first line to read:
_DEFINE A-Z AS INTEGER
I get:
2.000 seconds for Hypot
1.000 seconds for Math stuff
Now that's too perfect to be a coincidence?
PRINT USING "##.### seconds for Math stuff"; t3
- t2
-
Change line 13 to read:
c = SQR(a * a + b * b)
I get the results:
1.594 seconds for Hypot
0.328 seconds for Math stuff
There is definitely something that needs looked at in the _HYPOT source code.
-
What version of QB64? I get much different times than those. O_o!
-
Version 1.2 Revision 20180202/85 from git 1d0f920
-
Screenshot below. Hypot is much quicker on my machine -- almost to the point of your numbers being reversed compared to mine.
-
Yeah, that's spooky, the same 1.594 in opposite spots?
-
Difference is between QB64x32 and QB64x64. I normally program in the 64-bit version of QB64, which is what the screenshot above is for. Here's an image taken of the same code, same machine, with 32-bit QB64:
*********************
*********************
Hypot is faster in both cases, on my machine, but it's quite a bit slower with the 32-bit version.
-
Why are my numbers so far off then? Is it the version of 32bit QB64 I'm using?
-
Why are my numbers so far off then? Is it the version of 32bit QB64 I'm using?
No idea. I'm curious as heck now to see what results some other folks will generate with the same code. I've always had _HYPOT run much faster on my machine, and I *assumed* it behaved the same for all others. Let's wait and see how the speed tests turn out for a few other folks. ;)
-
Sounds good.
-
I just downloaded the latest build and ran the code. Version 1.2 dev build from git e490b1a
1.593 seconds for Hypot
1.429 seconds for Math stuff
-
If you don't mind, try this version and see what your times are: https://www.dropbox.com/s/f2ec7twbbhvg33v/QB64%20x64%20%2807-21-2018%29.7z?dl=1
It's the 64-bit version of QB64, and much faster with _HYPOT for me.
-
macOS (64bit, bare metal):
0.275 s _HYPOT
1.703 s Math stuff
Ubuntu (virtual machine) 64bit:
0.494 s _HYPOT
1.978 s Math stuff
Windows XP (virtual machine) 32bit:
2.088 s _HYPOT
1.813 s Math stuff
-
If you don't mind, try this version and see what your times are: https://www.dropbox.com/s/f2ec7twbbhvg33v/QB64%20x64%20%2807-21-2018%29.7z?dl=1
It's the 64-bit version of QB64, and much faster with _HYPOT for me.
WOW!
0.220 seconds for Hypot
1.484 seconds for Math stuff
When I change line 13 to:
c = SQR(a * a + b * b)
0.275 seconds for Hypot
0.165 seconds for Math stuff
-
Nice find Terry! I got nearly same results as Steve with ^2's but WOW! with a*a + b*b
-
I'm still ending up faster with _HYPOT than the plain math formula, but that may be because I've tweaked the compiler switches in the past for math speed (-ffast-math, I think, and maybe -o4 as well).
One important note with _HYPOT: It prevents rounding and overflow errors from occurring in the intermediate steps to getting your answer.
For example: X * X + Y * Y > the DOUBLE limit... Your answer would be wrong as it'd overflow down, before the SQR ever occurs.
Not that most people would ever run into this issue, but if your math is large enough, it could be an issue, and _HYPOT is supposed to not have that issue.
Edit: Wiki actually has a good explaination of it here: https://en.m.wikipedia.org/wiki/Hypot
-
Here are the results for my most-average-in-the-world laptop (Win10 64 bit) with last month's QB64 build and no math tweaks:
The _HYPOT command is several factors slower when I test it.
And I'm trying to parse Not that most people would ever run into this issue, but if your math is large enough, it could be an issue, and _HYPOT is supposed to not have that issue.
... so does the author believe this is a general and powerful command, or no? Is the DOUBLE limit part of its construction as opposed to float, long, integer, or some other type limit? (Maybe I didn't read carefully which is possible. Are you saying _HYPOT handles all the types without bias? My bad, it's been a minute!)
-
Why is the DOUBLE limit part of its construction as opposed to float, long, integer, or some other type limit? (Maybe I didnt read carefully which is possible.)
Double, I believe, because that's what gcc uses internally for these type of calculations.
Add a 8-byte value to a 8-byte value, and try and store it in a 8-byte return value... If the 2 numbers are too large, you get overflow.
Think of it like changing (a + b) / 2 into a + (b - a) / 2... In cases where a + b are too large for the internal return variable to hold, the math overflows and is wrong. a + (b - a) / 2 isn't going to have that issue.
*******************
In the end, it seems as if SQR(a * a + b * b) is ending up faster for most people, (which honestly shocks me from my personal results in the past), but _HYPOT is still the routine to use for extreme large/small/precision cases.
-
Looking at the Wiki link provided I can see why _HYPOT would be slower now because of the substitution needed to prevent overflow.
double hypot(double x,double y)
x = abs(x);
y = abs(y);
if (y > x) swap(x, y);
if (x == 0.0) return y;
double t = y / x;
return x * sqrt(1 + t * t);
-
Aye, thanks fellas. Makes a bit more sense now. Scared me for a second!
(I have a fantasy of computers having only one number type one day... I hate having to know things about programming that never explicitly arose from mathematics but are only still around due to tradition...)
-
Looking at the Wiki link provided I can see why _HYPOT would be slower now because of the substitution needed to prevent overflow.
double hypot(double x,double y)
x = abs(x);
y = abs(y);
if (y > x) swap(x, y);
if (x == 0.0) return y;
double t = y / x;
return x * sqrt(1 + t * t);
I think what the gcc compiler does is a little more:
IF x < y then
if x = 0 return y
return x * sqrt(1 + y / x * y / x)
Else
if y = 0 return x
return y * sqrt(1 + x / y * x/ y)
End If
Which saves a few function calls, but is still more complicated than the direct math would be.
-
Aha! There is a work around for neg numbers?
I was working circle fill routines with same formula as Terry had shown and got hung by negative value coming up somewhere in calculation both SQR and ^.5, crash.
Wait how can you get a neg when A * A + B * B would cancel it? Don't know but I had a circle fill routine that refused to work unless I loose time to check for negs or loose time calling ABS.
Hmm... now I wonder if, .... no I was still not using Octants back then.
But I see now the formula does use ABS calls, well the one from Wiki, if Steve is corrrect:
I think what the gcc compiler does is a little more:
IF x < y then
if x = 0 return y
return x * sqrt(1 + y / x * y / x)
Else
if y = 0 return x
return y * sqrt(1 + x / y * x/ y)
End If
Which saves a few function calls, but is still more complicated than the direct math would be.
Then gcc compiler might not be doing enough, I think the ABS calls are needed.
Come to think, I might have been getting negative numbers because the type I was using was too small?
350 * 350 > integer range but I don't think I was working in integers... I digress.
-
man all you guys got better machines than mine. between the two types the numbers are nearly identical for me.
3.35 _HYPOT
3.68 _OTHER (0.715 changing ^2 to *a,*b)
-
Squaring by exponentiation is slower than the straight a * a procedure. In any case for this function, I'd use that construction. as an inlined function, calculation is approximately 20% faster than _HYPOT. (7.849s versus 9.98s for _hypot) at n=10000. For convenience, perhaps. As a matter of algorithmic choice for _HYPOT, no.
-
In x64 Linux I get the _HYPOT version about twice as fast. If I change everything to use INTEGERs the math stuff version is about the same, whereas _HYPOT is now about 7 times faster (Terry: make sure you leave the timer variables as floats otherwise they'll be rounded to integers).
_HYPOT is implemented as a direct call to the C hypot() function. The manual states "The calculation is performed without undue overflow or underflow during the intermediate steps of the calculation", which supports what Steve was saying about intermediate overflow.
I traced the execution of _HYPOT and on my machine, at least, it's using SSE instructions to do the calculation. I'd be curious to know if perhaps 32 bit machines are doing more work because of their reduced register width to shunt the data around.
-
Linux Mint 19. just copied straight and run..
64bit 1.2qb64x64