Skip to content

Instantly share code, notes, and snippets.

# pkoppstein/BigInt.jq Last active Aug 17, 2019

BigInt library of functions for jq
 # Copyright (c) 2014-2015 Peter Koppstein (pkoppstein at gmail dot com) 2015.05.02 # # Permission is hereby granted, free of charge, to any person obtaining a copy # of this software and associated documentation files (the "Software"), to deal # in the Software without restriction, including without limitation the rights # to use, copy, modify, merge, publish, distribute, sublicense, and/or sell # copies of the Software, and to permit persons to whom the Software is # furnished to do so, subject to the following conditions: # # The above copyright notice and this permission notice shall be included in # all copies or substantial portions of the Software. # # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR # IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, # FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE # AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER # LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, # OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN # THE SOFTWARE. # # Credits: http://opensource.org/licenses/MIT (The MIT License (MIT) # This file is self-contained and provides these "BigInt" functions # for working with possibly-signed arbitrarily long decimal strings. # def negate: # def lessOrEqual(x; y): # x <= y # def long_add(x;y): # x+y # def long_minus(x;y): # x-y # def long_power(i): # .^i # def long_multiply(x;y) # x*y # def long_divide(x;y): # x/y => [q,r] # def long_div(x;y): # integer division # def long_mod(x;y): # % # def long_sqrt: # In all cases, x and y must be strings; . and i should be an integer or a string. def negate: if . == "0" or . == "+0" or . == "-0" then "0" elif type == "number" then (-.|tostring) else .[0:1] as \$s | if \$s == "-" then .[1:] elif \$s == "+" then "-" + .[1:] else "-" + . end end ; def lessOrEqual(num1; num2): def lenn(num1; num2): # for non-negatives (num1|length) as \$l1 | (num2|length) as \$l2 # for non-negatives of equal length, can use <= | \$l1 < \$l2 or (\$l1 == \$l2 and num1 <= num2); num1[0:1] as \$s1 | num2[0:1] as \$s2 | if num1 == num2 or (\$s1 == "-" and \$s2 != "-") then true elif (\$s1 != "-" and \$s2 == "-") then false elif (\$s1 == "-" and \$s2 == "-") then lenn( num2[1:]; num1[1:] ) else lenn(num1; num2) end; def long_add(num1; num2): def stripsign: .[0:1] as \$a | if \$a == "-" then [ -1, .[1:]] elif \$a == "+" then [ 1, .[1:]] else [1, .] end; # The workhorse assumes non-negative integers: def add(num1;num2): if (num1|length) < (num2|length) then add(num2;num1) else (num1 | explode | map(.-48) | reverse) as \$a1 | (num2 | explode | map(.-48) | reverse) as \$a2 | reduce range(0; num1|length) as \$ix (\$a2; # result ( \$a1[\$ix] + .[\$ix] ) as \$r | if \$r > 9 # carrying then .[\$ix + 1] = (\$r / 10 | floor) + (if \$ix + 1 >= length then 0 else .[\$ix + 1] end ) | .[\$ix] = \$r - ( \$r / 10 | floor ) * 10 else .[\$ix] = \$r end ) | reverse | map(.+48) | implode end ; # If input is a string, output a string; if input is an exploded # string, then output an exploded string; output the 9s complement plus 1, # e.g. "11" => "89" def complement_plus1: #  is "0", and 2*48 + 9 is 105: if type == "string" then explode | map(105 - .) | implode | long_add(.;"1") else map(105 - .) | implode | long_add(.;"1") | explode end ; # For num1 >= 0 and num2 >= 0 def minus(num1; num2): def ltrim: if length <= 1 then . elif .[0:1] == "0" then (.[1:]|ltrim) else . end ; if num1 == num2 then "0" elif num2 == "0" or num2 == "-0" then num1 elif num1 == "0" or num1 == "-0" then "-" + num2 else (num1|length) as \$l1 | (num2|length) as \$l2 | if \$l1 > \$l2 or (\$l1 == \$l2 and num1 > num2) then ("9"*(\$l1 - \$l2) + (num2|complement_plus1)) as \$c | (long_add(num1; \$c))[1:] | ltrim else "-" + minus(num2; num1) end end ; if num1 == "0" then num2 elif num2 == "0" then num1 else (num1|stripsign) as \$a1 | (num2|stripsign) as \$a2 | if \$a1*\$a2 == 1 then add(\$a1; \$a2) as \$sum | if \$a1 == 1 then \$sum else \$sum | negate end elif \$a1 == 1 then minus(\$a1; \$a2) else minus(\$a2 ;\$a1) end end ; def long_minus(x;y): long_add( x; y | negate); # multiply two decimal strings, which may be signed (+ or -) def long_multiply(num1; num2): def stripsign: .[0:1] as \$a | if \$a == "-" then [ -1, .[1:]] elif \$a == "+" then [ 1, .[1:]] else [1, .] end; def adjustsign(sign): if sign == 1 then . else "-" + . end; # mult/2 assumes neither argument has a sign def mult(num1;num2): (num1 | explode | map(.-48) | reverse) as \$a1 | (num2 | explode | map(.-48) | reverse) as \$a2 | reduce range(0; num1|length) as \$i1 ([]; # result reduce range(0; num2|length) as \$i2 (.; (\$i1 + \$i2) as \$ix | ( \$a1[\$i1] * \$a2[\$i2] + (if \$ix >= length then 0 else .[\$ix] end) ) as \$r | if \$r > 9 # carrying then .[\$ix + 1] = (\$r / 10 | floor) + (if \$ix + 1 >= length then 0 else .[\$ix + 1] end ) | .[\$ix] = \$r - ( \$r / 10 | floor ) * 10 else .[\$ix] = \$r end ) ) | reverse | map(.+48) | implode; (num1|stripsign) as \$a1 | (num2|stripsign) as \$a2 | if \$a1 == "0" or \$a2 == "0" then "0" elif \$a1 == "1" then \$a2|adjustsign( \$a1 * \$a2 ) elif \$a2 == "1" then \$a1|adjustsign( \$a1 * \$a2 ) else mult(\$a1; \$a2) | adjustsign( \$a1 * \$a2 ) end; # Emit (input)^i where input and i are non-negative decimal integers, represented as numbers and/or strings. # An error may be raised if i > 2^32 def long_power(i): # int is an integer def power(i): tostring as \$self | if i == 0 then "1" elif i == 1 then \$self elif (\$self == "0") then "0" elif (\$self == "1") then "1" else reduce range(1;i) as \$_ ( \$self; long_multiply(.; \$self) ) end; def check: # check that . is not way too big (2^28) if type == "number" and . <= 268435456 then . elif lessOrEqual(.; "268435456") then tonumber else error("long_power: \(.) is too large") end; if i == 0 or i == "0" then "1" else tostring as \$self | if i == 1 or i == "1" then \$self elif (\$self == "0") then "0" elif (\$self == "1") then "1" else (i|check) as \$i | if \$i < 4 then power(\$i) else (\$i|sqrt|floor) as \$j | (\$i - \$j*\$j) as \$k | long_multiply( power(\$j) | power(\$j) ; power(\$k) ) end end end; # return [quotient, remainder] # 0/0 = 1; n/0 => error def long_divide(x;y): # x/y => [q,r] def stripsign: .[0:1] as \$a | if \$a == "-" then [ -1, .[1:]] elif \$a == "+" then [ 1, .[1:]] else [1, .] end; def ltrim: if length <= 1 then . elif .[0:1] == "0" then (.[1:]|ltrim) else . end ; # divvy(num; yy) - input and output are [m, sum] where: # num and sum are strings representing non-negative integers; # On conclusion, assuming num and yy are positive, m is the maximum integer such that m * yy == sum <= num def divvy(num; yy): (num|ltrim) as \$n | if \$n == "0" then . else . as \$m | . as \$sum | long_add(\$sum; yy) as \$sum1 | if lessOrEqual(\$sum1; \$n) then [\$m + 1, \$sum1] | divvy(\$n; yy) else . end end; # [quotient; remainder] def _divide(x;y): # x and y are non-negative if x == y then ["1", "0"] elif y == "1" then [x, "0"] elif y == "0" then error("cannot divide \(x) by 0") else (x|length) as \$xlength | (y|length) as \$ylength # if the strings have the same length then we can use < | if \$xlength < \$ylength or ( \$xlength == \$ylength and x < y ) then [ "0", x ] else reduce range(0; \$xlength) as \$i ( ["",""]; # state: [q, r] . as \$q | (. + "0") as \$r | (long_add(\$r; x[\$i:\$i+1])) as \$num | [0, "0"] | divvy(\$num; y) | ( "-" + .) as \$negate | [ (\$q + (.|tostring)), long_add(\$num; \$negate) ] ) end | map(ltrim) end; # Ready at last: (x|stripsign) as \$sx | (y|stripsign) as \$sy | _divide(\$sx; \$sy) | if \$sx == 1 and \$sy == 1 then . elif \$sx == 1 and \$sy == -1 then . = (.|negate) elif \$sx == -1 and \$sy == -1 then . = (.|negate) else map(negate) end; def long_div(x;y): long_divide(x;y) | .; def long_mod(x;y): long_divide(x;y) | .; # The maximal integer whose square is less than or equal to the given input. def long_sqrt: . as \$n | ["1", \$n] # [div, div2] | last(recurse( . as \$div | . as \$div2 | if \$div == \$div2 then empty else long_div( long_add(\$div; long_div(\$n; \$div)); "2") | debug as \$y | if \$y == \$div or \$y == \$div2 then long_multiply(\$y; \$y) as \$yy | if \$yy == \$n then \$y elif lessOrEqual(\$n; \$yy) then long_minus(\$y; "1") else \$y end | [.,.] else [\$y, \$div] end end) | .) ;
to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.