Division issues with FB ULONGINTs?

[cbruce]

Is there a known issue with FB's division "/" operator and ULONGINT variables?

My environment:
FreeBASIC Compiler - Version 1.06.0 (11-29-2017), built for win64 (64bit)
Windows 10 64-bit

Division, "/", results are hit or miss - no consistency.
INT(x / ?), (the floor function), always returns a consistent answer for any divisor.
SHR always returns a consistent answer when using it to divide by multiples of 2.

Code: Select all

'18446744073709551610    ' Given x as this ULONGINT...
'--------------------
'9223372036854775808     ' FB  x/2     = ( __WRONG__ ? answer )
'9223372036854775805     ' C++ x/2     = ( Correct ? answer )
'9223372036854775805     ' FB INT(x/2) = ( Correct ? answer )
'9223372036854775805     ' FB x SHR 1  = ( Correct ? answer )

dim x as ULongInt
dim r as ULongInt
dim i as ULongInt

i = 4575728998270   'Random medium-size ULONGINT value
for x = i to i+9
print "---------------------------"
print "x          = "; x
print "---------------------------"
r = x / 2
print "x / 2      = "; r
r = int(x / 2)
print "int(x / 2) = "; r
r = x shr 1
print "x SHR 1    = "; r
print "--------"
r = x / 4
print "x / 4      = "; r
r = int(x / 4)
print "int(x / 4) = "; r
r = x shr 2
print "x SHR 2    = "; r
print "--------"
r = x / 3
print "x / 3      = "; r
r = int(x / 3)
print "int(x / 3) = "; r
print
next

I ran up against a wall when trying to port the PCG PRNG's advance/skip/jump functionality
to FB. I've looked at it on/off over the last few months and just now figured out that the
issue is that FB's "/" appears to be rounding differently and is not returning results consistent
with C++'s "/" when used with QWORDS (i.e. ULONGINT, uint64_t, ull, unsignedlonglong, whatever).

Does anyone know if this is a feature, or a bug, or just a difference that I will have to
always work around by using INT(ULONGINT / x) in the future?

Code: Select all

/'
Test output:
I've set a "?" next to the results that are in question.

D:\>Test_ULONGINT_DIV_error.exe

---------------------------
x          = 4575728998270
---------------------------
x / 2      = 2287864499135
int(x / 2) = 2287864499135
x SHR 1    = 2287864499135
--------
x / 4      = 1143932249568  ?
int(x / 4) = 1143932249567
x SHR 2    = 1143932249567
--------
x / 3      = 1525242999423
int(x / 3) = 1525242999423

---------------------------
x          = 4575728998271
---------------------------
x / 2      = 2287864499136  ?
int(x / 2) = 2287864499135
x SHR 1    = 2287864499135
--------
x / 4      = 1143932249568  ?
int(x / 4) = 1143932249567
x SHR 2    = 1143932249567
--------
x / 3      = 1525242999424  ?
int(x / 3) = 1525242999423

---------------------------
x          = 4575728998272
---------------------------
x / 2      = 2287864499136
int(x / 2) = 2287864499136
x SHR 1    = 2287864499136
--------
x / 4      = 1143932249568
int(x / 4) = 1143932249568
x SHR 2    = 1143932249568
--------
x / 3      = 1525242999424
int(x / 3) = 1525242999424

---------------------------
x          = 4575728998273
---------------------------
x / 2      = 2287864499136
int(x / 2) = 2287864499136
x SHR 1    = 2287864499136
--------
x / 4      = 1143932249568
int(x / 4) = 1143932249568
x SHR 2    = 1143932249568
--------
x / 3      = 1525242999424
int(x / 3) = 1525242999424

---------------------------
x          = 4575728998274
---------------------------
x / 2      = 2287864499137
int(x / 2) = 2287864499137
x SHR 1    = 2287864499137
--------
x / 4      = 1143932249568
int(x / 4) = 1143932249568
x SHR 2    = 1143932249568
--------
x / 3      = 1525242999425  ?
int(x / 3) = 1525242999424

---------------------------
x          = 4575728998275
---------------------------
x / 2      = 2287864499138  ?
int(x / 2) = 2287864499137
x SHR 1    = 2287864499137
--------
x / 4      = 1143932249569  ?
int(x / 4) = 1143932249568
x SHR 2    = 1143932249568
--------
x / 3      = 1525242999425
int(x / 3) = 1525242999425

---------------------------
x          = 4575728998276
---------------------------
x / 2      = 2287864499138
int(x / 2) = 2287864499138
x SHR 1    = 2287864499138
--------
x / 4      = 1143932249569
int(x / 4) = 1143932249569
x SHR 2    = 1143932249569
--------
x / 3      = 1525242999425
int(x / 3) = 1525242999425

---------------------------
x          = 4575728998277
---------------------------
x / 2      = 2287864499138
int(x / 2) = 2287864499138
x SHR 1    = 2287864499138
--------
x / 4      = 1143932249569
int(x / 4) = 1143932249569
x SHR 2    = 1143932249569
--------
x / 3      = 1525242999426  ?
int(x / 3) = 1525242999425

---------------------------
x          = 4575728998278
---------------------------
x / 2      = 2287864499139
int(x / 2) = 2287864499139
x SHR 1    = 2287864499139
--------
x / 4      = 1143932249570  ?
int(x / 4) = 1143932249569
x SHR 2    = 1143932249569
--------
x / 3      = 1525242999426
int(x / 3) = 1525242999426

---------------------------
x          = 4575728998279
---------------------------
x / 2      = 2287864499140  ?
int(x / 2) = 2287864499139
x SHR 1    = 2287864499139
--------
x / 4      = 1143932249570  ?
int(x / 4) = 1143932249569
x SHR 2    = 1143932249569
--------
x / 3      = 1525242999426
int(x / 3) = 1525242999426

'/

Thanks,
CBruce

[Josep Roca]

For integer division use \ instead of /.

[cbruce]

Thanks, Josep... And I'm a dummy for not talking about using "\" instead of INT(x/?). I was just so irritated when I finally figured out that it appears to me that C++ "/" is actually using floor() internally when evaluating ULONGINT division that my mind fell back to more of a math implementation since FB doesn't have a function that is named "floor".

I had been thinking that since FB is now generating C on the backend, that I would be free from strange side effects at the operator level, etc.

So I want to make sure that I won't run into any other low level side-effects when porting from C++. This issue took me a while to figure out since there are some oddities in the C++ code that I thought were probably the cause of the problem.

Does anyone know for sure that C++ actually does use floor() during its unsigned long integer division? Or is there some other decision process that it uses for rounding that is going to come back and bite me in the posterior?

[fxm]

With FreeBASIC:
r = x / N
x / N returns always a Double.
When the compiler converts the float result of division (a Double) to an integer value (r is an Ulongint), the closest integer value is always used for assignment.

[srvaldez]

hello cbruce
using the C compiler explorer https://godbolt.org
the following C code compiled with x86-64 gcc 7.3 with option -O2

Code: Select all

unsigned long long int myfunc (unsigned long long int a, unsigned long long int b)
{
  return (a/b);
}

produces the following asm code

Code: Select all

        mov     rax, rdi
        xor     edx, edx
        div     rsi
        ret

[counting_pine]

(EDIT: I can see other people have posted explanations since I started to write this, but it may be useful.)

In both C and FreeBASIC, there are two kinds of division.

Integer division uses integer math, and integer CPU instructions, and returns an integer. The decimal part is never actually calculated, and rounding is always towards 0 (or at least that's how it works on Intel platforms).

Floating-point division uses floating-point math, on floating-point operands, and returns a floating-point number. The decimal part can be rounded away using one of a couple of different rounding (or integer type conversion) methods.

The difference between C and FB, is this:
- C chooses the type of division based on the operands (integer division if they are both integer, or floating-point division otherwise).
- FB chooses the type based on the division operator chosen ('/' or '\'), and converts the operands accordingly before performing the division.

In either C or FB, if the result of a float division is stored in an integer, then the result must be converted to an integer type. This is done implicitly in both languages.
Usually C rounds towards 0, and FB rounds to the nearest, choosing the even number if the decimal is 0.5, but if I recall correctly, this can be configured (depending on the platform/compiler) with some specific function calls.

FB's conversion is done with something like 'cast(integer, a)' - or 'cint(a)' for short. C's conversion is done with something like '(int)a'.

In FB, if you write 'a = b / c', with integer variables, the result will be calculated as: a = cast(integer, cast(double, a) / cast(double, b)).
But if you write 'a = b \ c' with integer variables, the calculation needs no conversion and is much simpler, literally just: a = b \ c.

You should try to avoid floating-point division with 64-bit integer, because when you convert any odd number between 2^53 and 2^64, you may lose bits of precision off the end, because double-precision values can't hold that many bits.

[cbruce]

Great information folks! Now I can get back to work on the conversion and see if I can finally get something useful to post.

[TeeEmCee]

In either C or FB, if the result of a float division is stored in an integer, then the result must be converted to an integer type. This is done implicitly in both languages.
Usually C rounds towards 0, and FB rounds to the nearest, choosing the even number if the decimal is 0.5, but if I recall correctly, this can be configured (depending on the platform/compiler) with some specific function calls.

Only sometimes.
Because FB's rounding semantics matches the default behaviour of x86's FISTP instruction, FB will compile to a FISTP instruction on x86 and x86_64 (both gas and gcc backends when using x87). FISTP is affected by the rounding mode in the FPU control word (defaulting to round-to-nearest), so you can change it with _controlfp() on Windows and _FPU_GETCW under glibc (GNU), etc.
On the other hand C compilers will call function like ftol to get the required C semantics, which will temporarily set the FPU control word, and so is slow (see e.g. here).
However, the SSE equivalent instruction always truncates, matching the C semantics. (It seems alternative instructions for controlling rounding are added in later SSE iterations). Note that GCC will use SSE by default if available.
On non-x86 hardware, FB calls nearbyint which sets the FPU control word, so again you can't adjust it.

Also, on x86 hardware you can't change the behaviour of integer division; IDIV always truncates.

Plus if you try to change runtime behaviour like then, then compiler optimisations will change your results.

However, GCC has -fno-rounding-math (set by -ffast-math) and Visual C++ has /Qifist which you can use to make them use FISTP instead of some slow conversion function.

Also note that in C, behaviour of division with a negative number is implementation defined :( Meanwhile in FB we don't exactly have a spec, but around here such undefined behaviour would be considered a bug.