Created
February 22, 2022 19:00
-
-
Save jido/6d734fb3545e9a166dc0fe8fb13784ba to your computer and use it in GitHub Desktop.
A way to represent integers up to 2^125 in 64 bits, based on the Posit representation of numbers.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Note: this was tested on Arm64. It should work on any common 64 bit architecture. | |
# Note 2: typemin(Int64) means NaN and is not handled by the function. | |
extend64to128 = function(w :: Int64) | |
x = abs(w) | |
big = (x << 1) >> 63 # -1 if the number is extended (bit 62 set) | |
neg = (w >>> 62) | 1 # 11 for negative number, 01 for positive | |
rg = leading_zeros(~x << 1) # count the regime bits | |
# That's where it really starts. | |
# A posit number with 0-length exponent starts with a variable amount of regime bits (all 1's or all 0's), | |
# followed by a stop bit (opposite of regime) then the fractional part. In our case we are multiplying the | |
# posit by 2^62 (inverse of smallest non-zero posit) to produce integers so we are only interested in 1's | |
# regime. | |
# In the first step, we normalise the fractional part by shifting it to bits 61... | |
nm = (w << rg) & ~(1 << 63) | |
# Then we add the implied binary digit 1 in bit 62. We also insert the sign bit at position 63 | |
base = nm ⊻ (neg << 62) | |
# All that remains to do is to shift by the regime amount a second time - the largest the regime the | |
# highest the precision loss. Variable "big" is used as a mask to chose between a "small" integer (< 2^62) | |
# and a "large" integer (2^62 to 2^125). | |
(Int128(base & big) << (rg-1)) | Int128(w & ~big) | |
end | |
Examples: | |
julia> extend64to128(123456) | |
123456 | |
julia> extend64to128(0) | |
0 | |
julia> extend64to128(-1) | |
-1 | |
julia> extend64to128(-9999) | |
-9999 | |
julia> extend64to128(2^62) | |
4611686018427387904 | |
julia> extend64to128(2^62+1) | |
4611686018427387906 | |
julia> extend64to128(2^62+50) | |
4611686018427388004 | |
julia> extend64to128(2^62+100) | |
4611686018427388104 | |
julia> extend64to128(2^63-100) | |
238845655492602070912402831144124416 | |
julia> extend64to128(2^63-50) | |
477691310985204141824805662288248832 | |
julia> extend64to128(2^63-7) | |
3323069989462289682259517650700861440 | |
julia> extend64to128(2^63-6) | |
3987683987354747618711421180841033728 | |
julia> extend64to128(2^63-5) | |
4652297985247205555163324710981206016 | |
julia> extend64to128(2^63-4) | |
5316911983139663491615228241121378304 | |
julia> extend64to128(2^63-3) | |
7975367974709495237422842361682067456 | |
julia> extend64to128(2^63-2) | |
10633823966279326983230456482242756608 | |
julia> extend64to128(2^63-1) | |
42535295865117307932921825928971026432 | |
julia> extend64to128(1-2^63) | |
-42535295865117307932921825928971026432 | |
julia> Int128(2)^125 | |
42535295865117307932921825928971026432 | |
julia> Int128(2)^123 | |
10633823966279326983230456482242756608 |
ghost
commented
Feb 23, 2022
Ha ha, function syntax — thanks @ninjin for catching that!
You are welcome. I suspect what happened here is that using an untyped, non-constant variable to hold the function in the global scope caused an allocation at the call site. While I did not use it to spot this, you can use the @code_*
macros to help spot these kinds of issues when writing performance critical code.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment