search

google / neuroglancer

WebGL-based viewer for volumetric data
Apache License 2.0
1.02k stars 283 forks source link

fix(uint64): avoid rounding errors in Uint64.toString with large high values #577

Closed chrisj closed 2 months ago

chrisj commented 2 months ago

https://github.com/google/neuroglancer/blob/daf82f3ad4af2007e96faca35143cd5ec986bf60/src/util/uint64.ts#L105

if vHigh > Number.MAX_SAFE_INTEGER / 0x100000000 vHigh *= trueBase; will exceed Number.MAX_SAFE_INTEGER. Math.floor(vHigh / lowBase) will then start to return whole numbers when the fraction is very close to 0 or 1. When it is due to it being 1, javascript rounds up which then causes the floor operation to fail. BigInt safely handle the division + floor operation.

For example: base 3, low 0, high 92064593 92064593 * trueBase / 3486784401 = 113403746.99999998652053164327...

92064593 * trueBase / 3486784401 = 113403747 (in javascript)
Math.floor(92064593 * trueBase / lowBase) = 113403747
92064593 * trueBase % lowBase = 3486784382
chrisj commented 2 months ago

This is the most minimal change that appears to fix the problem. It would give me a little more peace of mind if BigInt was used before the multiplication of vHigh *= trueBase. BigInt is able to recover the true value but it's a little concerning.

92064593 * 0x100000000 = 395414416054550500
BigInt(395414416054550500) = 395414416054550528n
jbms commented 2 months ago

vHigh *= trueBase is always exact since trueBase is a power of two, so we are just adding to the exponent field.

However, I didn't think about the issue of rounding up for the subsequent division.

Ultimately it may make sense to eliminate Uint64 entirely and just use bigint in Neuroglancer now. But your fix looks good.