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