uint.fz
# This file is part of the Fuzion language implementation.
#
# The Fuzion language implementation is free software: you can redistribute it
# and/or modify it under the terms of the GNU General Public License as published
# by the Free Software Foundation, version 3 of the License.
#
# The Fuzion language implementation is distributed in the hope that it will be
# useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
# License for more details.
#
# You should have received a copy of the GNU General Public License along with The
# Fuzion language implementation. If not, see <https://www.gnu.org/licenses/>.
# -----------------------------------------------------------------------
#
# Tokiwa Software GmbH, Germany
#
# Source code of Fuzion standard library feature uint
#
# Author: Michael Lill (michael.lill@tokiwa.software)
#
# -----------------------------------------------------------------------
# unsigned integer of arbitrary size, including zero
# represented by its bit sequence
private:public uint (public b Sequence u32, _ unit) : has_interval
is
# the actually relevant data of this uint.
# irrelevant zeros at start are dropped.
# zero is represented by the empty list.
data := b.drop_while (x -> x = u32 0)
# bitwise operations
# bitwise and
public fixed infix & (other uint) uint =>
(b1, b2) := equalize other
uint (b1.zip b2 (x,y)->x&y) unit
# bitwise or
public fixed infix | (other uint) uint =>
(b1, b2) := equalize other
uint (b1.zip b2 (x,y)->x|y) unit
# bitwise xor
public fixed infix ^ (other uint) uint =>
(b1, b2) := equalize other
uint (b1.zip b2 (x,y)->x^y) unit
# shift operations
# shift right
public fixed infix >> (other uint) uint
pre other ≤ uint i32.max.as_u64
=>
if other = uint.zero
thiz
else if other ≥ uint 32
discard := other.as_i32 / 32
(uint (data.take data.count-discard) unit) >> (other % (uint 32))
else
shift := other.as_u32
(l,_) := data
.reduce ((list u32).empty, u32 0) (r,t ->
(res, carry_over) := r
next := t>>shift | carry_over
(res ++ [next], t << (u32 32)-shift)
)
uint l unit
# shift left
public fixed infix << (other uint) uint
pre other ≤ uint i32.max.as_u64
=>
if other = uint.zero
thiz
else if other ≥ uint 32
uint (data ++ zeros (other.as_i32 / 32)) unit << other % (uint 32)
else
shift := other.as_u32
(l,carry_over) := data
.reverse
.reduce ((list u32).empty, u32 0) (r,t ->
(res, carry_over) := r
next := t<<shift | carry_over
([next] ++ res, t >> ((u32 32)-shift))
)
uint ([carry_over] ++ l) unit
# return two sequences of equal length
# by prepending zero(s) to the shorter sequence
private equalize(other uint)
post result.values.0.count = result.values.1.count
=>
if other.data.count < data.count
(data.as_list, zeros data.count-other.data.count ++ other.data)
else
(zeros other.data.count-data.count ++ data, other.data.as_list)
# divide with remainder the two given positive ints
# returns the quotient and the remainder
# NYI performance: https://cs.opensource.google/go/go/+/refs/tags/go1.19:src/math/big/natdiv.go
private divide_with_remainder (divisor uint) tuple uint uint
pre divisor > uint.zero
=>
if thiz = uint.zero
(uint.zero, uint.zero)
else if thiz < divisor
(uint.zero, thiz)
else if thiz = divisor
(uint.one, uint.zero)
else
# The idea is to shift the divisor left as
# far as possible so that the subtraction of this and
# the shifted divisor is still positive.
# This is done recursively and the results
# are added up.
highest_bit_diff uint := highest_bit - divisor.highest_bit
shift := if thiz -! (divisor << highest_bit_diff) then highest_bit_diff else highest_bit_diff-uint.one
remainder := thiz - (divisor << shift)
(q,rem) := remainder.divide_with_remainder divisor
((uint.one << shift) + q, rem)
# the highest 1 bit in this integer
# example: uint 0 => 0
# example: uint 1 => 1
# example: uint 8 => 4
public highest_bit uint
=>
if thiz = uint.zero
uint.zero
else
uint ((data.count.as_u32 - 1) * 32 + data.first.highest_bit).as_u64
# add two unsigned ints
public fixed infix + (other uint) uint =>
(b1, b2) := equalize other
(d, _, _) := ([u32 0] ++ b1)
.reverse_list
.reduce (((list u32).empty), ([u32 0] ++ b2).reverse_list, u64 0) (r, t ->
(bits, rest, carry_over) := r
s := t.as_u64 + rest.first.as_u64 + carry_over
([s.low32bits] ++ bits, (rest.drop 1), (s>>32))
)
uint d unit
# subtract other from this unsigned int
public fixed infix - (other uint) uint
pre thiz ≥ other
=>
two_pow_32 := ((u64 1)<<32)
(b1, b2) := equalize other
(r, _) := b1
.zip b2 (x, y -> (x,y))
.reverse_list
.reduce ((list u32).empty, u64 0) (r,t ->
(minuend, subtrahend) := t
(res, carry_over) := r
difference := two_pow_32 + minuend.as_u64 - subtrahend.as_u64 - carry_over
([difference.low32bits] ++ res, if difference ≥ two_pow_32 then u64 0 else u64 1)
)
uint r unit
# return an array of length n
# initialized with u32 zeros.
private zeros(n i32) =>
array n (_ -> u32 0)
# NYI make faster: https://en.wikipedia.org/wiki/Multiplication_algorithm#Computational_complexity_of_multiplication
# multiply these unsigned ints
public fixed infix * (other uint) uint =>
data
.reverse_list
.indexed
.map ((x) ->
(i, v) := x
other
.data
.reverse
.indexed
.map (ox ->
(oi,ov) := ox
tmp := v.as_u64 * ov.as_u64
uint ([(tmp>>32).low32bits , tmp.low32bits] ++ zeros i+oi) unit
)
)
.flat_map uint (x -> x)
.fold uint.sum
# divide these unsigned ints
public fixed infix / (other uint) uint
pre other != uint.zero
=>
(quotient,_) := (divide_with_remainder other)
quotient
# modulo
# returns the remainder of the division
public fixed infix % (other uint) uint =>
(_,remainder) := (divide_with_remainder other)
remainder
# exponentation operator:
# this uint to the power of other
public fixed infix ** (other uint) uint
=>
if other = uint.zero
uint.one
else if other = uint.one
thiz
else
if other %% (uint 2)
tmp := thiz**(other / uint 2)
tmp * tmp
else
thiz * (thiz**(other-uint.one))
# equality: are these unsigned integers equal?
#
fixed type.equality(a, b uint) bool =>
a.data.count = b.data.count &&
((a.data.zip b.data (c,d -> c = d)) ∀ (x->x))
# total order
#
fixed type.lteq(a, b uint) =>
if a.data.count = b.data.count
a.data
# zip the two equally long lists of digits
.zip b.data (c,d -> (c,d))
# skip to first unequal
.drop_while (x -> (c,d) := x; c = d)
# compare
.map (x -> (c,d) := x; c ≤ d)
# fallback, if all are equal
.first true
else
a.data.count < b.data.count
# checks if operations are allowed
public fixed prefix -! bool => thiz = uint.zero
public fixed infix +! (other uint) bool => true
public fixed infix -! (other uint) bool => thiz ≥ other
public fixed infix *! (other uint) bool => true
public fixed infix /! (other uint) bool => other != uint.zero
public fixed infix %! (other uint) bool => true
public fixed infix **!(other uint) bool => true
# exponentation always works, even though it might be
# slow for large numbers
public fixed infix **?(other uint) num_option uint => thiz ** other
public fixed infix **^(other uint) uint => thiz ** other
public fixed type.zero uint =>
uint [u32 0] unit
public fixed type.one uint =>
uint [u32 1] unit
public thiz => uint b unit
# this uint as an i32
public as_i32 i32
pre as_u32 ≤ i32.max.as_u32
=>
as_u32.as_i32
# this uint as an i64
public as_i64 i64
=>
as_u64.as_i64
# this uint as an u8
public as_u8 u8
=>
as_u32.as_u8
# does this uint fit in 32 bits?
public fits_in_u32 =>
data.count ≤ 1
# this uint as an u32
public as_u32 u32
pre fits_in_u32
=>
data.first (u32 0)
# does this uint fit in 64 bits?
#
public fits_in_u64 =>
data.count ≤ 2
# this uint as an u64
public as_u64 u64
pre fits_in_u64
=>
if data.count = 2
data[1].as_u64<<32 | data[0].as_u64
else
(data.first 0).as_u64
# this uint as an int
public as_int int
=>
int num.plus (uint b unit)
# this uint as a string, may contain leading zeros
#
private as_string0 String =>
mrd := uint 1_000_000_000
(q, rem) := uint.this.divide_with_remainder mrd
if q = uint.zero
(rem.data.first (u32 0)).as_string
else
q.as_string0 + (rem.data.first (u32 0)).as_string.pad_codepoint_start 9 "0"
public redef as_string String =>
if thiz = uint.zero
"0"
else
as_string0
# helper feature to init uint from an u64
type.from_u64(val u64) uint =>
uint [(val>>32).low32bits , val.low32bits] unit
# shorthand to create an uint via an u64
public uint (val u64) uint =>
uint.from_u64 val