Efficient Mathematics

[TerryRitchie]

Since my sprite library is using hella math at places I decided to see if I could make it more efficient. I assumed that integer division would be faster than regular division and that reciprocal multiplication would be faster than both. When I ran the following code I was a bit surprised.

Turns out regular division is usually faster in QB64?

Code: QB64: [Select]

1. t = TIMER
2. FOR i = 1 TO 1000000
3.     FOR k = 1 TO 100
4.         j = i \ 100
5.     NEXT k
6. NEXT i
7. t2 = TIMER
8. FOR i = 1 TO 1000000
9.     FOR k = 1 TO 100
10.         j = i / 100
11.     NEXT k
12. NEXT i
13. t3 = TIMER
14. FOR i = 1 TO 1000000
15.     FOR k = 1 TO 100
16.         j = i * .01
17.     NEXT k
18. NEXT i
19. t4 = TIMER
20.  
21. PRINT USING "##.#### integer division"; t2 - t
22. PRINT USING "##.#### regular division"; t3 - t2
23. PRINT USING "##.#### reciprocal multiplication"; t4 - t3
24.  

[TerryRitchie]

It appears that using integers makes a difference:

Code: QB64: [Select]

1. DEFINT A-Z
2.  
3. t# = TIMER
4. FOR i = 1 TO 32767
5.     FOR k = 1 TO 4096
6.         j = i \ 100
7.     NEXT k
8. NEXT i
9. t2# = TIMER
10. FOR i = 1 TO 32767
11.     FOR k = 1 TO 4096
12.         j = i / 100
13.     NEXT k
14. NEXT i
15. t3# = TIMER
16. FOR i = 1 TO 32767
17.     FOR k = 1 TO 4096
18.         j = i * .01
19.     NEXT k
20. NEXT i
21. t4# = TIMER
22.  
23. PRINT USING "##.#### integer division"; t2# - t#
24. PRINT USING "##.#### regular division"; t3# - t2#
25. PRINT USING "##.#### reciprocal multiplication"; t4# - t3#
26.  

Edit: Is there a place in the Wiki that perhaps points out the best math to use in each situation?

[Pete]

In QuickBASIC, which the QB64 language was based on, using DEFINT was a common practice to assign less memory to each variable speed up calculations. I used DEFINT H-K with DEFSTR A-G for many programs to speed up results and to save memory by not having to include the "$" behind string variables that started with the letters A-G. It saved typing, too.

I don't think I've seen any speed comparisons for various math methods. Most speed topics seem to be about sorting, file processing, etc. I think if you want really fast sprite movements involving large blocks of memory, that _MEM statement would be worth looking into. I think Steve has a good deal of familiarity with that one. QuickBASIC was difficult to get enough speed out of for complex gaming routines. The sad part is the ones people did create in QB were often too fast for me. :(

Pete

[codeguy]

Witth a precalculated inverse table, division by inverse multiplication is roughly 20% faster at n=33m+. This method eats a LOT of memory for the 20% gain. Timed, (125/128)s, precalculated table, (75/64)s, using 32-bit operands and double prescision tables.

At single precision table, the difference is quite a bit more significant, being 11/128s, versus (75/64)s, nearly 14 times faster. I'd use the single-precision inverse table *IFF* speed is your passion. Take my word for it. I've tested it already. These numbers apply whether assignment is to double or single.

Assignment to integer using single-precision inverse table is 25% faster than division.

Single prescision inverse table seems to be a very good bet for speed AND accuracy. Oh yeah, some changes to the size of the table had to be made because I wanted to reduce effects of background processes on timings, so those are for 33m+. My answer still stands: single-precision inverse table, regardless of precision of operands.

[Pete]

And someone please thank codeguy for that analysis. He's our only Asian member. If we lose him, we're stuck with my crappy Caucasian math answers: 1 + 1 = ... I'll post back, later.

Pete :D

[codeguy]

Always glad to be the non-communist South Korean analysis dude. I'd do a more in-depth but this clearly suffices. There are permutations of precisions that COULD work, but the fiddling that requires is a violin best not played. Back to my Stradivarius :). Oh yeah, one more sort algorithm is on the way: randomized median of 3 partitioning iterative QuickSort. Now saving you (8-10)%. Then Lomuto as featured in Introduction to Algorithms. One can never have too many sorting algorithms (some are WICKED faster than ones in any textbook). And a variant of BucketSort, that great memory hog, except less of a hog and more akin to the fat guy eating at a buffet but not feeling quite himself *skips dessert AND the diet Coke* :).

:) ASIANS ROCK :)

And because 2.16GHz can still move dat azz with well-designed code. Go HP :).