Cross-platformly deterministic to-the-power-of function

Questions about the LÖVE API, installing LÖVE and other support related questions go here.
Forum rules
Before you make a thread asking for help, read this.
User avatar
wolfboyft
Prole
Posts: 20
Joined: Sat Oct 21, 2017 5:28 pm
Location: London
Contact:

Cross-platformly deterministic to-the-power-of function

Post by wolfboyft »

With the same starting conditions and the same set of inputs every frame, my game must play through the exact same session on any platform. In fact, the demo replay feature will just be auto-feeding the game recorded inputs!
Because it must be the same on any platform, floats are out of the question; I use fixed-point numbers (32 represents 1.)
But I've come across a need to use exponentiation.

How can I make a pow(x, y) function determinstically for fixeds?
Using a few values in a lookup table is OK. I'll need integer powers to be 100% accurate (i could use a separate (for loop multiplication) algorithm for them?) Can sqrt be part of the same function? (pow(x, 0.5) or rather, pow(x, 16))

Thanks in advance!
(Sorry if it sounds like I'm demanding spoon-fed information.)
Tachytaenius
SPlice
Prole
Posts: 48
Joined: Thu Jul 28, 2011 8:53 am

Re: Cross-platformly deterministic to-the-power-of function

Post by SPlice »

why not just write a pow() function, something like this (not sure if this works because I didn't try it but it seems like the concept should be sound as long as e >=0)

Code: Select all

 
pow(n,e) 
  local total = 1 
  if e > 0 then  
    for i = 1, e do 
      total = total * n 
    end 
  end
  return total 
end
User avatar
pgimeno
Party member
Posts: 3544
Joined: Sun Oct 18, 2015 2:58 pm

Re: Cross-platformly deterministic to-the-power-of function

Post by pgimeno »

I wouldn't be so wary about floats. Lua numbers are all IEEE-754 doubles in all platforms supported by LÖVE. Note you're using floats either way; in Lua 5.1 you don't have integers.

Note that if division can go wrong with floats, it can with "integers" as well, unless you implement your own (slow) division routine.

As for pow, for integer exponents you can use repeated squaring and multiplying (similar to how you multiply two binary numbers by repeated doubling and adding). For arbitrary exponents, you have the same problem as with division; you'll have to look up some numeric approximation methods and implement one. For square roots you can use Newton's method, assuming you have a robust division algorithm: if x is an approximation to the square root of n, then (n/x+x)/2 is a better approximation. https://en.wikipedia.org/wiki/Methods_o ... uare_roots

My advice is to evaluate how many differences in floating point rounding you get in the different platforms you want to support, to see whether it's really worth going the hard and slow way of performing operations using your functions for everything.
User avatar
raidho36
Party member
Posts: 2063
Joined: Mon Jun 17, 2013 12:00 pm

Re: Cross-platformly deterministic to-the-power-of function

Post by raidho36 »

Doubles can represent integers exactly up to 53 bits length.
User avatar
wolfboyft
Prole
Posts: 20
Joined: Sat Oct 21, 2017 5:28 pm
Location: London
Contact:

Re: Cross-platformly deterministic to-the-power-of function

Post by wolfboyft »

To continue on my path to fixeds...

I'm not going to allow any errors to accumulate; let's say that's my self-set challenge rather than an aspect of my mind.
Newton's method sounds appealing. I have not yet been convinced by the idea that I need pow(x, y) where y is anything but 0.5 (sqrt,) anyway.

As for whether I should just use floats...

Applying floor, ceil et cetera to floating points doesn't work according to this thing that someone said to me:

"The problem with any rounding method is that it there are points x where a value slightly below x rounds down and a value slightly above x rounds up, and therefore any calculation errors near x are magnified."

I do not know whether this applies to truncation, though. Maybe if I truncate to a "safe" number of decimal places... like, three or four...
But isn't "truncate" just another rounding method? I don't understand.
Tachytaenius
User avatar
zorg
Party member
Posts: 3436
Joined: Thu Dec 13, 2012 2:55 pm
Location: Absurdistan, Hungary
Contact:

Re: Cross-platformly deterministic to-the-power-of function

Post by zorg »

Truncation removes the fractional part without modifying the part to the left of the decimal point. math.floor basically does that, for positive numbers; for negative, it would be math.ceil (and zero's already a whole number).

Also, what was your logic behind making 32 equal 1? Wouldn't 100 = 1 make more sense? Since in that case, you could represent up to the hundredths place exactly (with decimal numbers, i mean)

If you want to, you could always use luajit's ffi and use actual non-float numbers, since the operations on them would be exact. (well, your usual add sub mul (integer-)div stuff, that is.

On the other hand, if you plan on having an authoritative server, then all this is moot, since then you can always use the server to fix any minute drift, once a second or so, so you'd be free to use floating point numbers; the only issue there would be to implement a non-deltatime-sensitive game loop, and there are tons of examples of that (and you should already have that in place anyway).
Me and my stuff :3True Neutral Aspirant. Why, yes, i do indeed enjoy sarcastically correcting others when they make the most blatant of spelling mistakes. No bullying or trolling the innocent tho.
User avatar
wolfboyft
Prole
Posts: 20
Joined: Sat Oct 21, 2017 5:28 pm
Location: London
Contact:

Re: Cross-platformly deterministic to-the-power-of function

Post by wolfboyft »

So I guess that won't work then...

Why 32 and not 100? When I was making my sine lookup table: I like powers of two and 32 is good-enough resolution.

FFI? I tried looking in to it once. Didn't really get very far.

The authoritative server idea isn't what I want to use; it doesn't work with the challenge I set myself/my philosophy.
Tachytaenius
User avatar
pgimeno
Party member
Posts: 3544
Joined: Sun Oct 18, 2015 2:58 pm

Re: Cross-platformly deterministic to-the-power-of function

Post by pgimeno »

wolfboyft wrote: Sat May 26, 2018 11:21 am Applying floor, ceil et cetera to floating points doesn't work according to this thing that someone said to me:

"The problem with any rounding method is that it there are points x where a value slightly below x rounds down and a value slightly above x rounds up, and therefore any calculation errors near x are magnified."
That sentence is true. but it doesn't mean that different platforms do the rounding differently. It's not usual to find platforms that don't apply IEEE-754 rules for rounding. The default rounding mode is round to nearest or even, which should work the same in all architectures. If you find a platform that doesn't apply round-to-nearest-or-even, you'd have reasons to worry.

[Edit: Besides, you need to do rounding yourself when working with fixed point too, in particular when multiplying and dividing, so that sentence applies to the rounding you perform as well.]

Example of rounding to nearest or even (if you get this result in all architectures you want to support, you don't have to worry). The value is 2^52, past which no numbers have decimals.

Code: Select all

> x="4503599627370496"   
> print(string.format("%.17g", tonumber(string.match(x,"%d+"))+0.5))
4503599627370496
> print(string.format("%.17g", tonumber(string.match(x,"%d+"))+1.5))
4503599627370498
> print(string.format("%.17g", tonumber(string.match(x,"%d+"))+0.5001))
4503599627370497
(I've used string.match to prevent any optimization that pre-calculates the results)

The rounding mode isn't the only hurdle, though. IEEE-754 semantics require that +, -, * and / be the exact rounded result. It's possible to run into an architecture that doesn't support these semantics, but these are not common; see https://stackoverflow.com/questions/729 ... cc#7295955

As noted there, Intel pre-SSE2 FPUs used an internal 80 bit format that could potentially cause miscalculations due to double rounding (first to 80 bits and then to 64 bits), and that could give a wrong result in some special cases while dividing. The other arithmetic operations (+, -, *) are safe when done on integers.

However, it won't be easy finding platforms without IEEE semantics, or running into practical cases where double rounding causes a problem. It won't be easy to find a platform that doesn't apply round-to-nearest-or-even either. That's why I advised you to try in the platforms you intend to support, to see if they implement the semantics you need.

FFI won't help here. The data types in memory will be correct, but while they are in registers they are floating-point, and when dividing, they will be divided in floating point.

Edit:
zorg wrote: Sat May 26, 2018 12:10 pmAlso, what was your logic behind making 32 equal 1? Wouldn't 100 = 1 make more sense? Since in that case, you could represent up to the hundredths place exactly (with decimal numbers, i mean)
A power of two is a good choice actually. First, it allows bit.rshift for dividing; second, since the underlying float is binary, the division by a power of two will be exact.
User avatar
zorg
Party member
Posts: 3436
Joined: Thu Dec 13, 2012 2:55 pm
Location: Absurdistan, Hungary
Contact:

Re: Cross-platformly deterministic to-the-power-of function

Post by zorg »

pgimeno wrote: Sat May 26, 2018 1:49 pm FFI won't help here. The data types in memory will be correct, but while they are in registers they are floating-point, and when dividing, they will be divided in floating point.
Are you positive that using signed/unsigned integers and doing division on them doesn't actually do integer division due to them being C datatypes?
Me and my stuff :3True Neutral Aspirant. Why, yes, i do indeed enjoy sarcastically correcting others when they make the most blatant of spelling mistakes. No bullying or trolling the innocent tho.
User avatar
pgimeno
Party member
Posts: 3544
Joined: Sun Oct 18, 2015 2:58 pm

Re: Cross-platformly deterministic to-the-power-of function

Post by pgimeno »

zorg wrote: Sat May 26, 2018 2:18 pmAre you positive that using signed/unsigned integers and doing division on them doesn't actually do integer division due to them being C datatypes?
No, I stand corrected. I didn't even know you could do operations with ctypes. You're right, that's one way. It doesn't seem to respect types, though.

Code: Select all

$ cat > test.lua
local ffi = require 'ffi'

local a = ffi.new('int32_t', 37)
local b = ffi.new('int32_t', 17)
local c = ffi.new('int32_t', 1)
for i = 1, 70 do
  c = c * a
  c = c / b
end

print(string.format("%.17g", tonumber(c)))
^D
$ luajit -j dump main.lua 

<snip>

->LOOP:
55a65331ffe0  mov rsi, [rsp+0x8]
55a65331ffe5  mov rdi, rax
55a65331ffe8  imul rdi, rbx
55a65331ffec  call 0x55a662076760	->lj_carith_divi64
55a65331fff1  add ebp, +0x01
55a65331fff4  cmp ebp, +0x46
55a65331fff7  jle 0x55a65331ffe0	->LOOP
55a65331fff9  jmp 0x55a65331001c	->3
---- TRACE 1 stop -> loop

-84041051210270160
Edit: The equivalent in C:

Code: Select all

#include <stdint.h>
#include <stdio.h>
int main(int argc, const char *argv[])
{
    int64_t a = 37;
    int64_t b = 17;
    int64_t c = 1;
    int i;
    for (i = 1; i <= 70; i++)
    {
        c = c * a;
        c = c / b;
    }
    printf("%lld\n", c);
}
prints -84041051210270157, which shows that tonumber() converts to float at the last step, but that's expectable.
Post Reply

Who is online

Users browsing this forum: No registered users and 39 guests