Skip to content

Instantly share code, notes, and snippets.

@jido
Created February 22, 2022 19:00
Show Gist options
  • Save jido/6d734fb3545e9a166dc0fe8fb13784ba to your computer and use it in GitHub Desktop.
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.
# 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
Copy link

ghost commented Feb 23, 2022

haneda> julia
               _
   _       _ _(_)_     |  Documentation: https://docs.julialang.org
  (_)     | (_) (_)    |
   _ _   _| |_  __ _   |  Type "?" for help, "]?" for Pkg help.
  | | | | | | |/ _` |  |
  | | |_| | | | (_| |  |  Version 1.6.3 (2021-09-23)
 _/ |\__'_|_|_|\__'_|  |  Official https://julialang.org/ release
|__/                   |

julia> 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
#1 (generic function with 1 method)

julia> @allocated extend64to128(123456)
1257747

julia> @allocated extend64to128(123456)
32

julia> 
haneda> julia
               _
   _       _ _(_)_     |  Documentation: https://docs.julialang.org
  (_)     | (_) (_)    |
   _ _   _| |_  __ _   |  Type "?" for help, "]?" for Pkg help.
  | | | | | | |/ _` |  |
  | | |_| | | | (_| |  |  Version 1.6.3 (2021-09-23)
 _/ |\__'_|_|_|\__'_|  |  Official https://julialang.org/ release
|__/                   |

julia> function extend64to128(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
extend64to128 (generic function with 1 method)

julia> @allocated extend64to128(123456)
0

julia> @allocated extend64to128(123456)
0

julia> 

@jido
Copy link
Author

jido commented Feb 23, 2022

Ha ha, function syntax — thanks @ninjin for catching that!

Copy link

ghost commented Feb 24, 2022

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