BigInt library of functions for jq

BigInt.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: # [48] 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[0]*$a2[0] == 1 then 
      add($a1[1]; $a2[1]) as $sum
      | if $a1[0] == 1 then $sum else $sum | negate end
    elif $a1[0] == 1 then minus($a1[1]; $a2[1])
    else minus($a2[1] ;$a1[1])
    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[1] == "0" or  $a2[1] == "0" then "0"
    elif $a1[1] == "1" then $a2[1]|adjustsign( $a1[0] * $a2[0] )
    elif $a2[1] == "1" then $a1[1]|adjustsign( $a1[0] * $a2[0] )
    else mult($a1[1]; $a2[1]) | adjustsign( $a1[0] * $a2[0] )
    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
        .[0] as $m | .[1] 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]
              .[0] as $q | (.[1] + "0") as $r
              | (long_add($r; x[$i:$i+1])) as $num
              | [0, "0"] | divvy($num; y) 
              | ( "-" + .[1]) as $negate
              | [ ($q + (.[0]|tostring)), long_add($num; $negate) ]
            )
        end
      | map(ltrim)
    end;

  # Ready at last:
    (x|stripsign) as $sx
  | (y|stripsign) as $sy
  | _divide($sx[1]; $sy[1])
  | if   $sx[0] == 1 and $sy[0] == 1 then .
    elif $sx[0] == 1  and $sy[0] == -1 then .[0] = (.[0]|negate)
    elif $sx[0] == -1 and $sy[0] == -1 then .[1] = (.[1]|negate) 
    else map(negate)
    end;

def long_div(x;y):
  long_divide(x;y) | .[0];

def long_mod(x;y):
  long_divide(x;y) | .[1];

# 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( .[0] as $div | .[1] 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) | .[0]) ;