note description: "[ An arbitrary precision library for integer numbers. Creation make_from_string, make_from_integer64, make_from_integer32, Queries absolute: BIG_INTEGER as_integer32: INTEGER as_integer64: INTEGER divide (other: BIG_INTEGER): BIG_INTEGER gcd (other: BIG_INTEGER): BIG_INTEGER is_equal (other: BIG_INTEGER): BOOLEAN is_greater alias ">" (other: [like Current] BIG_INTEGER): BOOLEAN is_greater_equal alias ">=" (other: [like Current] BIG_INTEGER): BOOLEAN is_less alias "<" (other: BIG_INTEGER): BOOLEAN is_less_equal alias "<=" (other: [like Current] BIG_INTEGER): BOOLEAN max (other: [like Current] BIG_INTEGER): [like Current] BIG_INTEGER min (other: [like Current] BIG_INTEGER): [like Current] BIG_INTEGER minus alias "-" (other: BIG_INTEGER): BIG_INTEGER opposite alias "-": BIG_INTEGER out: STRING plus alias "+" (other: BIG_INTEGER): BIG_INTEGER power alias "^" (other: INTEGER): BIG_INTEGER product alias "*" (other: BIG_INTEGER): BIG_INTEGER quotient alias "//" (other: BIG_INTEGER): BIG_INTEGER remainder alias "\\" (other: BIG_INTEGER): BIG_INTEGER square: BIG_INTEGER ]" author: "JSO" date: "$17 July, 2018$" revision: "$0.91$" class BIG_INTEGER inherit COMPARABLE redefine is_equal, default_create, out end create make_from_string, make_from_integer64, make_from_integer32, default_create convert make_from_string ({STRING_8}), make_from_integer64 ({INTEGER_64}), make_from_integer32 ({INTEGER_32}), as_integer64: {INTEGER_64}, as_integer32: {INTEGER_32}, out: {STRING_8} feature {NONE} -- constructors default_create -- Create BIG_INTEGER 0 local empty: STRING_8 do empty := "0" item := "0" ensure then item.is_equal ("0") end make_from_string (s: STRING_8) -- Create a BIG_INTEGER from string s require non_empty: not s.is_empty has_correct_format: is_string_int (s) do item := s.twin normalize end make_from_integer32 (int: INTEGER_32) -- Create a BIG_INTEGER from int do make_from_string (int.out) end make_from_integer64 (int: INTEGER_64) -- Create a BIG_INTEGER from int do make_from_string (int.out) end feature -- comparison is_equal (other: BIG_INTEGER): BOOLEAN -- Is other equal to Current? do Result := item_fix.is_equal (other.item_fix) end is_less alias "<" (other: BIG_INTEGER): BOOLEAN -- Is Current less than other? local r1i, r2i, d1, d2: INTEGER_32 r1, r2: BIG_INTEGER do r1 := Current.clone_me r2 := other.clone_me if r1.item.item (1) = '-' and r2.item.item (1) /= '-' then Result := True elseif r1.item.item (1) /= '-' and r2.item.item (1) = '-' then Result := False elseif r1.item.item (1) = '-' and r2.item.item (1) = '-' then r1.negate r2.negate Result := r2 < r1 else r1.align_decimal (r2) r1.align_whole (r2) Result := False from r1i := 1 r2i := 1 until r1i > r1.item.count or r2i > r2.item.count loop d1 := to_digit (r1.item.item (r1i)) d2 := to_digit (r2.item.item (r2i)) if d1 < d2 then Result := True r1i := r1.item.count + 1 elseif d1 > d2 then Result := False r1i := r1.item.count + 1 end r1i := r1i + 1 r2i := r2i + 1 end end end feature -- operations plus alias "+" (other: BIG_INTEGER): BIG_INTEGER -- Returns the result of adding other to Current local d1, d2, answer: DECIMAL do create d1.make_from_big_int (Current) create d2.make_from_big_int (other) answer := d1 + d2 Result := answer.as_big_int end minus alias "-" (other: BIG_INTEGER): BIG_INTEGER -- Returns the result of subtracting other from Current -- Was declared in BIG_INTEGER as synonym of subtract. local d1, d2, answer: DECIMAL do create d1.make_from_big_int (Current) create d2.make_from_big_int (other) answer := d1 - d2 Result := answer.as_big_int end subtract (other: BIG_INTEGER): BIG_INTEGER -- Returns the result of subtracting other from Current -- Was declared in BIG_INTEGER as synonym of minus. local d1, d2, answer: DECIMAL do create d1.make_from_big_int (Current) create d2.make_from_big_int (other) answer := d1 - d2 Result := answer.as_big_int end product alias "*" (other: BIG_INTEGER): BIG_INTEGER -- Returns the result of multiplying Current with other local d1, d2, answer: DECIMAL do create d1.make_from_big_int (Current) create d2.make_from_big_int (other) d1.set_precision (d1.get_precision + d2.get_precision) answer := d1 * d2 Result := answer.as_big_int end quotient alias "//" (other: BIG_INTEGER): BIG_INTEGER -- Returns the result of dividing Current from other -- Was declared in BIG_INTEGER as synonym of divide. require denominator_non_zero: other /~ zero local d1, d2, answer: DECIMAL do create d1.make_from_big_int (Current) create d2.make_from_big_int (other) answer := d1 / d2 answer := answer.floor Result := answer.as_big_int end divide (other: BIG_INTEGER): BIG_INTEGER -- Returns the result of dividing Current from other -- Was declared in BIG_INTEGER as synonym of quotient. require denominator_non_zero: other /~ zero local d1, d2, answer: DECIMAL do create d1.make_from_big_int (Current) create d2.make_from_big_int (other) answer := d1 / d2 answer := answer.floor Result := answer.as_big_int end square: BIG_INTEGER -- Returns the result of Current * Current do Result := Current * Current end power alias "^" (other: INTEGER_32): BIG_INTEGER -- Returns the result of raising Current to the power other -- Was declared in BIG_INTEGER as synonym of exp. require power_non_zero: other >= 0 do if other = 0 then Result := one else Result := Current across 1 |..| (other - 1) as i loop Result := Result * Current end end end exp (other: INTEGER_32): BIG_INTEGER -- Returns the result of raising Current to the power other -- Was declared in BIG_INTEGER as synonym of power. require power_non_zero: other >= 0 do if other = 0 then Result := one else Result := Current across 1 |..| (other - 1) as i loop Result := Result * Current end end end remainder alias "\\" (other: BIG_INTEGER): BIG_INTEGER -- Return the result of Current mod other (Consistent with WolframAlpha's mod) require non_zero: other /~ zero local tmp: BIG_INTEGER do if Current < zero and other > zero then tmp := Current.absolute \\ other Result := other - tmp elseif Current > zero and other < zero then tmp := Current \\ other.absolute Result := other + tmp else Result := Current - ((Current // other) * other) end end gcd (other: BIG_INTEGER): BIG_INTEGER -- Return the positive greatest common divisor of Current and other require both_not_zero: Current /~ zero or other /~ zero local a, b: BIG_INTEGER do a := absolute b := other.absolute if b ~ zero then Result := a elseif a ~ zero then Result := b elseif a > b then Result := b.gcd (a \\ b) else Result := gcd (b \\ a) end end negate -- negates the number local tmp: STRING_8 do if item.item (1) = '-' then tmp := item.substring (2, item.count) item := tmp.twin else item.insert_character ('-', 1) end end absolute: BIG_INTEGER -- Returns the absolute value of Current do if Current >= Current.zero then Result := Current.clone_me else Result := opposite.clone_me end ensure Result >= Result.zero end feature -- conversion as_integer64: INTEGER_64 -- represent as a integer 64 require valid_int64: out.is_integer_64 do Result := item.to_integer_64 end as_integer32: INTEGER_32 -- represent as a integer 32 require valid_int32: out.is_integer_32 do Result := item.to_integer_32 end feature -- queries out: STRING_8 -- New string containing terse printable representation -- of current object do Result := item.twin end opposite alias "-": BIG_INTEGER -- unary minus do create Result.make_from_string (item) Result.negate end identity alias "+": BIG_INTEGER -- unary plus do create Result.make_from_string (item) end zero: BIG_INTEGER -- neutral element for "+" and "-" do create Result.make_from_string ("0") end one: BIG_INTEGER -- neutral element for "*" and "/" do create Result.make_from_string ("1") end divisible (other: BIG_INTEGER): BOOLEAN -- may current object be divided by other? do Result := not other.is_equal (zero) end is_natural: BOOLEAN -- Is Current a natural number? do Result := is_integer and Current >= zero end is_natural1: BOOLEAN -- Is `Current a Natural1 number? do Result := is_integer and Current >= one end is_integer: BOOLEAN -- Is string representation item an int? do Result := item.index_of ('.', 1) = 0 end feature {BIG_INTEGER} -- private fields item: STRING_8 -- string representation clone_me: BIG_INTEGER local l_s: STRING_8 do create l_s.make_from_string (item) create Result.make_from_string (item.twin) end feature {BIG_INTEGER} -- private methods item_fix: STRING_8 -- Fix for negative zero do if item ~ "-0" then Result := "0" else Result := item end end is_valid_string (s: STRING_8): BOOLEAN -- check if the given string is of the correct format require non_void: s /= Void non_empty: not s.is_empty local seendot: BOOLEAN i: INTEGER_32 do seendot := False Result := True from i := 1 until i > s.count loop if s.item (i) = '-' then if i > 1 then Result := False i := s.count + 1 end elseif s.item (i) = '.' then if i = s.count or seendot then Result := False i := s.count + 1 end seendot := True elseif not s.item (i).is_digit then Result := False i := s.count + 1 end i := i + 1 end end normalize -- standardizes the format of the number require non_empty: not item.is_empty local i, inspos, dotpos, firstnonzeropos, lastnonzeropos: INTEGER_32 seenminus, prependzero, hasdot: BOOLEAN whole, fraction, empty, tmp, zerostr: STRING_8 do empty := "" zerostr := "0" seenminus := False prependzero := False from i := 1 until i > item.count loop if item.item (i) = '-' then seenminus := True elseif item.item (i) = '.' then if i = 1 or seenminus then prependzero := True end end i := i + 1 end if prependzero then inspos := 1 if seenminus then inspos := 2 end item.insert_character ('0', inspos) end if (seenminus) then negate end dotpos := item.index_of ('.', 1) if dotpos = 0 then hasdot := False whole := item.twin fraction := empty.twin else hasdot := True tmp := item.substring (1, dotpos - 1) whole := tmp.twin tmp := item.substring (dotpos + 1, item.count) fraction := tmp.twin end if not whole.is_empty then firstnonzeropos := whole.count + 1 from i := 1 until i > whole.count loop if whole.item (i) /= '0' then firstnonzeropos := i i := whole.count + 1 end i := i + 1 end if firstnonzeropos = whole.count + 1 then whole := zerostr.twin else tmp := whole.substring (firstnonzeropos, whole.count) whole := tmp.twin end end if not fraction.is_empty then lastnonzeropos := -1 from i := fraction.count until i < 1 loop if fraction.item (i) /= '0' then lastnonzeropos := i i := 0 end i := i - 1 end if lastnonzeropos = -1 then fraction := empty.twin else tmp := fraction.substring (1, lastnonzeropos) fraction := tmp.twin end end item := whole.twin if hasdot and not fraction.is_empty then item.append (".") item.append (fraction) end if seenminus and not item.is_equal ("0") then item.insert_character ('-', 1) end end to_digit (ch: CHARACTER_8): INTEGER_32 -- converts a character to a digit local chzero: CHARACTER_8 do chzero := '0' Result := ch.code - chzero.code end to_char (d: INTEGER_64): CHARACTER_8 -- converts a digit to a character local chzero: CHARACTER_8 do chzero := '0' Result := (chzero.code.to_integer_64 + d).to_character_8 end align_decimal (other: BIG_INTEGER) -- used to align the fractional parts of the given parameters local mydotpos, otherdotpos, myprec, otherprec, numtopad, i: INTEGER_32 pad: detachable STRING_8 do mydotpos := item.index_of ('.', 1) otherdotpos := other.item.index_of ('.', 1) if mydotpos /= 0 and otherdotpos /= 0 then myprec := item.count - mydotpos otherprec := other.item.count - otherdotpos if myprec /= otherprec then pad := Void if myprec < otherprec then pad := item else pad := other.item end numtopad := (myprec - otherprec).abs from i := 1 until i > numtopad loop pad.append_character ('0') i := i + 1 end end elseif mydotpos /= 0 or otherdotpos /= 0 then if mydotpos /= 0 then myprec := item.count - mydotpos else myprec := 0 end if otherdotpos /= 0 then otherprec := other.item.count - otherdotpos else otherprec := 0 end pad := Void if myprec < otherprec then pad := item else pad := other.item end numtopad := (myprec - otherprec).abs pad.append_character ('.') from i := 1 until i > numtopad loop pad.append_character ('0') i := i + 1 end end end align_whole (other: BIG_INTEGER) -- used to align the integer parts of the given parameters local mydotpos, otherdotpos, mywholelength, otherwholelength, menegoffset, othernegoffset, inspos, numtopad, i: INTEGER_32 meneg, otherneg: BOOLEAN pad: detachable STRING_8 do mydotpos := item.index_of ('.', 1) otherdotpos := other.item.index_of ('.', 1) meneg := item.item (1) = '-' otherneg := other.item.item (1) = '-' if mydotpos /= 0 then if meneg then menegoffset := 1 else menegoffset := 0 end mywholelength := mydotpos - menegoffset - 1 else mywholelength := item.count end if otherdotpos /= 0 then if otherneg then othernegoffset := 1 else othernegoffset := 0 end otherwholelength := otherdotpos - othernegoffset - 1 else otherwholelength := other.item.count end if mywholelength /= otherwholelength then pad := Void if mywholelength < otherwholelength then pad := item else pad := other.item end inspos := 1 if pad.item (1) = '-' then inspos := inspos + 1 end numtopad := (mywholelength - otherwholelength).abs from i := 1 until i > numtopad loop pad.insert_character ('0', inspos) i := i + 1 end end end feature {RATIONAL, ES_TEST} -- export to rational Default_precision: INTEGER_32 = 0 -- inherited from VALUE real_division (other: BIG_INTEGER): DECIMAL require other_non_zero: other /~ zero local curr_dec, other_dec, res: DECIMAL do create curr_dec.make_from_string (out) create other_dec.make_from_string (other.out) res := curr_dec / other_dec Result := res end feature -- is_string_int is_string_int (s: STRING_8): BOOLEAN -- Is the given string a representation of big integer? require non_empty: not s.is_empty local seendot: BOOLEAN i: INTEGER_32 do seendot := False Result := True from i := 1 until i > s.count loop if s.item (i) = '-' then if i > 1 then Result := False i := s.count + 1 end elseif s.item (i) = '.' then Result := False elseif not s.item (i).is_digit then Result := False i := s.count + 1 end i := i + 1 end end invariant Default_precision = 0 is_integer note copyright: "Copyright (c) SEL, York University" license: "MIT" todo: "[ integer division \\ is veru ineficient. Fpr js algorithm see: www.javascripter.net/math/calculators/100digitbigintcalculator.htm and {TEST_INT_JSO}t51. To generate large random numbers: python3 import random random.getrandbits(128) -- 128 bits ]" end -- class BIG_INTEGER
Generated by ISE EiffelStudio