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 module: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=0 # bitwise operations # bitwise and public fixed redef infix & (other uint) uint => (b1, b2) := equalize other uint (b1.zip b2 x,y->x&y) unit # bitwise or public fixed redef infix | (other uint) uint => (b1, b2) := equalize other uint (b1.zip b2 x,y->x|y) unit # bitwise xor public fixed redef infix ^ (other uint) uint => (b1, b2) := equalize other uint (b1.zip b2 x,y->x^y) unit # shift operations # shift right public fixed redef infix >> (other uint) uint => check other ≤ uint i32.max.as_u64 if other = uint.zero uint.this 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 ((Sequence 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 redef infix << (other uint) uint => check other ≤ uint i32.max.as_u64 if other = uint.zero uint.this 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 ((Sequence u32).empty, u32 0) r,t-> (res, co) := r next := t<<shift | co ([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 equalize(other uint) post debug: result.values.0.count = result.values.1.count => if other.data.count < data.count (data, zeros data.count-other.data.count ++ other.data) else (zeros other.data.count-data.count ++ data, other.data) # 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 fixed divide_with_remainder (divisor uint) tuple uint uint pre safety: divisor > uint.zero => if uint.this = uint.zero (uint.zero, uint.zero) else if uint.this < divisor (uint.zero, uint.this) else if uint.this = 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 uint.this -! (divisor << highest_bit_diff) then highest_bit_diff else highest_bit_diff-uint.one remainder := uint.this - (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 fixed highest_bit uint => if uint.this = uint.zero uint.zero else uint ((data.count.as_u32 - 1) * 32 + data.first.get.highest_bit).as_u64 # add two unsigned ints public fixed redef infix + (other uint) uint => (b1, b2) := equalize other (d, _, _) := ([u32 0] ++ b1) .reverse .reduce (((Sequence u32).empty), ([u32 0] ++ b2).reverse, u64 0) r,t-> (bits, rest, carry_over) := r s := t.as_u64 + rest.first.get.as_u64 + carry_over ([s.low32bits] ++ bits, (rest.drop 1), (s>>32)) uint d unit # subtract other from this unsigned int public fixed redef infix - (other uint) uint => two_pow_32 := ((u64 1)<<32) (b1, b2) := equalize other (s, _) := b1 .zip b2 (x, y -> (x,y)) .reverse .reduce ((Sequence 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 s unit # return an array of length n # initialized with u32 zeros. 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 redef infix * (other uint) uint => data .reverse .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 id .fold uint.sum # divide these unsigned ints public fixed redef infix / (other uint) uint => (quotient, _) := (divide_with_remainder other) quotient # modulo # returns the remainder of the division public fixed redef infix % (other uint) uint => (_, remainder) := (divide_with_remainder other) remainder # exponentation operator: # this uint to the power of other public fixed redef infix ** (other uint) uint => if other = uint.zero uint.one else if other = uint.one uint.this else if other %% (uint 2) tmp := uint.this**(other / uint 2) tmp * tmp else uint.this * (uint.this**(other-uint.one)) # equality: are these unsigned integers equal? # public fixed redef type.equality(a, b uint) bool => a.data.count = b.data.count && ((a.data.zip b.data (c,d -> c = d)) ∀ id) # total order # public fixed redef 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 redef prefix -! bool => uint.this = uint.zero public fixed redef infix -! (other uint) bool => uint.this ≥ other # exponentiation always works, even though it might be # slow for large numbers public fixed redef infix **?(other uint) option uint => uint.this ** other public fixed redef infix **^(other uint) uint => uint.this ** other public fixed redef type.zero uint => uint [u32 0] unit public fixed redef type.one uint => uint [u32 1] unit # this uint as an i32 public as_i32 i32 pre debug: 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 redef as_u8 u8 => as_u32.as_u8 # does this uint fit into an u8? # public redef fits_in_u8 => data.count ≤ 1 && data[0].fits_in_u8 # this uint as an u32 public fixed as_u32 u32 pre debug: (uint.this ≤ uint.type.from_u32 u32.max) => data.first 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 debug: fits_in_u64 => if data.count = 2 data[1].as_u64<<32 | data[0].as_u64 else (data.first 0).as_u64 # does this uint fit into an u128? public fits_in_u128 => data.count ≤ 4 # this uint as an u128 public as_u128 u128 pre debug: fits_in_u128 => n := data.count bits := [u32 0].cycle.take (4-n) ++ data u128 (bits[3].as_u64<<32 | bits[2].as_u64) (bits[1].as_u64<<32 | bits[0].as_u64) # does this uint fit into an i128? public fits_in_i128 => data.count < 4 | (data.count = 4 && ((data[0] & i32.min.cast_to_u32) = u32 0)) # this uint as an i128 public as_i128 i128 pre debug: fits_in_i128 => n := data.count bits := [u32 0].cycle.take (4-n) ++ data i128 (bits[0].as_u64<<32 | bits[1].as_u64).cast_to_i64 (bits[2].as_u64<<32 | bits[3].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 # as_string0 String => mrd := uint 1_000_000_000 (q, rem) := uint.this.divide_with_remainder mrd if q = uint.zero (rem.data.first 0).as_string else q.as_string0 + (rem.data.first 0).as_string.pad_codepoint_start 9 "0" public fixed redef as_string String => if uint.this = uint.zero "0" else as_string0 # helper feature to init uint from an u32 public fixed redef type.from_u32(val u32) uint => uint [val] unit # 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