_______ __ _______
| | |.---.-..----.| |--..-----..----. | | |.-----..--.--.--..-----.
| || _ || __|| < | -__|| _| | || -__|| | | ||__ --|
|___|___||___._||____||__|__||_____||__| |__|____||_____||________||_____|
on Gopher (inofficial)
(HTM) Visit Hacker News on the Web
COMMENT PAGE FOR:
(HTM) Bitwise conversion of doubles using only FP multiplication and addition (2020)
sjrd wrote 8 hours 7 min ago:
Interesting. When compiling Scala.js to ECMAScript 5, we still have an
implementation of bitwise floating point conversions based on double
operations and integer shifts. [1] We also use a lookup table for
powers of 2, and don't use anything but primitives (no log or pow,
notably). We do have a few divisions, but I see now how I could turn
them into multiplications. Dealing with subnormals is tricky because
the inverse of the subnormal powers of 2 are not representable.
We have one loop: a binary search in the table of powers of 2 for the
double-to-bits conversion. It has a fixed number of iterations. I had
tried to unroll it, but that did not perform any better.
I'll have to dig more to understand how they got rid of the
comparisons, though.
I wonder whether their implementation would be faster than ours. At the
time I wrote our conversions, they beat every previous implementation I
was aware of hands down.
(HTM) [1]: https://github.com/scala-js/scala-js/blob/v1.20.2/linker-priva...
dougall wrote 2 hours 49 min ago:
Hi, author here. My version definitely shouldn't be faster unless
something very weird is going on with the runtime (though I think
with the benefit of hindsight some further optimisation of it is
possible). I have never seen a good use for this, aside from as a
proof that it is possible, but I can imagine it coming up if, say,
you wanted to write an exploit for an esoteric programming language
runtime.
If you still maintain this code and want to optimise it, I don't
think you should need a full powers-of-two table, just having log(n)
powers of two should do in a pattern like:
if (v > 2**1024) { v *= 2**-1024; e += 1024; }
if (v > 2**512) { v *= 2**-512; e += 512; }
...
That's a straightforward memory saving and also leaves v normalised,
so gives you your fraction bits with a single multiplication or
division. This is a little less simple than I'm making it look,
because in reality you end up moving v to near the subnormal range,
or having to use a different code path if v < 1 vs if v >= 2 or
something. But otherwise, yeah, the code looks good.
sjrd wrote 1 hour 18 min ago:
Thanks for the feedback, and congrats on your achievement.
We do still maintain this code, although it is deprecated now.
Even with the unrolled tests, we would still keep the table for the
decoding operation, I believe. But it's true that it would at the
same time provide the normalized value. That could be beneficial.
augusteo wrote 11 hours 23 min ago:
I love these "what if you only had X" puzzles. The constraint here (no
bit access, only FP multiply and add) sounds impossible until you
realize rounding behavior carries information.
The edge cases around negative zero and infinities make sense. Those
values break the mathematical properties you'd need to distinguish
them.
lifthrasiir wrote 12 hours 53 min ago:
Recommended readings:
Jim McCann, Tom Murphy VII, The fluint8 Software Integer Library. [1]
Tom Murphy VII, GradIEEEnt half decent.
(HTM) [1]: https://tom7.org/papers/fluint.pdf
(HTM) [2]: https://tom7.org/grad/murphy2023grad.pdf
avadodin wrote 3 hours 26 min ago:
Nice.
Also Tom Murphy the Seventh.
Odds on his child's name being Tom?
(DIR) <- back to front page