Results 1 to 5 of 5

Thread: Big-Integer for Simba (No Plugins Required)

  1. #1
    Join Date
    Feb 2011
    Location
    The Future.
    Posts
    5,600
    Mentioned
    396 Post(s)
    Quoted
    1598 Post(s)

    Default Big-Integer for Simba (No Plugins Required)

    I wrote this class for doing arithmetic with extremely large numbers. It can of course be optimised but meh.. It's fast enough for all intents and purposes..


    Simba Code:
    type
      BigInteger = record
        sign: ShortInt;
        digits: string;
      end;

    type
      TString = String; //work-around for a lape bug..

    Function TString.Reverse(): String;
    var
      C: Char;
      L, H: PChar;
    begin
      if (self.size() < 1) then
        exit;

      L := @self[1];
      H := @self[self.size()];
      while (L < H) do
      begin
        C := H^;
        H^ := L^;
        L^ := C;
        H -= 1;
        L += 1;
      end;
      Result := self;
    end;

    Function TString.Erase(Index, Amount: Integer = 1): String;
    Begin
      Delete(self, Index, Amount);
      Result := self;
    End;

    Function TString.Size(): Integer;
    Begin
      Result := Length(Self);
    End;


    Function BigInteger.Init(value: Int64): BigInteger;
    Begin
      Result := self;
      if (value = 0) then
        sign := 0
      else if (value > 0) then
        sign := 1
      else
        sign := -1;

      digits := ToStr(value);
      if (self.isNegative()) then
        digits.Erase(0);
      digits.Reverse();
    End;

    Function BigInteger.Init(value: UInt64): BigInteger; overload;
    Begin
      Result := self;
      if (value = 0) then
        sign := 0
      else if (value > 0) then
        sign := 1;

      digits := ToStr(value).Reverse();
    End;

    Function BigInteger.Init(value: Integer): BigInteger; overload
    Begin
      Result := self.Init(Int64(value));
    End;

    Function BigInteger.Init(value: UInt32): BigInteger; overload;
    Begin
      Result := self.Init(UInt64(value));
    End;

    Function BigInteger.Init(value: String): BigInteger; overload;
    var
      I: Integer;
    Begin
      Result := Self;
      self.sign := 0;
      if (value.size() > 0) then
      begin
        self.sign := 1;
        self.digits := value;

        if (self.digits[1] = '-') then
          self.sign := -1

        if ((self.digits[1] = '+') or (self.digits[1] = '-')) then
          self.digits.Erase(0);
      end;

      self.digits.Reverse();
      self.Normalise();
      For I := 1 To self.digits.size() Do
      begin
        if ((Ord(digits[I]) < $30) or (Ord(digits[I]) > $39)) then
        begin
          self.sign := 0;
          self.digits := '0';
        end;
      end;
    End;

    Function BigInteger.Init(other: BigInteger): BigInteger; overload;
    Begin
      self.sign := other.sign;
      self.digits := other.digits;
    End;

    Function BigInteger.Clone(): BigInteger;
    Begin
      Result := self.Init(self);
    End;

    Function BigInteger.IsNeutral(): Boolean;
    Begin
      Result := Sign = 0;
    End;

    Function BigInteger.IsPositive(): Boolean;
    Begin
      Result := Sign > 0;
    End;

    Function BigInteger.IsNegative(): Boolean;
    Begin
      Result := Sign < 0;
    End;

    Function BigInteger.Normalise(): BigInteger;
    var
      I: Integer;
    Begin
      Result := Self;
      For I := self.digits.size() DownTo 1 Do
      begin
        if (self.digits[I] <> '0') then
          break;
        self.digits.Erase(I);
      end;

      if (self.digits.size() < 1) then
      begin
        self.sign := 0;
        self.digits := '0';
      end;
    End;

    Function BigInteger.toDigit(Index: Integer): Integer;
    Begin
      if ((Index > 0) and (Index <= self.digits.size())) then
        Result := Ord(self.digits[Index]) - $30;
    End;

    Function BigInteger.toString(): String;
    Begin
      Result := toStr(self);
    End;

    Function toString(var other: BigInteger): String; override;
    Begin
      if (other.digits.size() < 1) Then
      begin
        Result := inherited(other);
      end else
        begin
          Result := other.Digits;
          Result.Reverse();
          if (other.isNegative()) then
            Result := '-' + Result;
        end;
    End;

    Function BigInteger.isLessThan(var other: BigInteger): Boolean;
    var
      I: Integer;
    Begin
      Result := false;
      if (self.isNeutral() or other.isNeutral()) then
      begin
        if (self.isNeutral()) then
          exit(other.isPositive())
        else
          exit(self.isNegative());
      end;

      if (sign <> other.sign) then
        exit(self.isNegative());

      if (digits.size() <> other.digits.size()) then
        exit(((self.digits.size() < other.digits.size()) and self.isPositive()) or ((self.digits.size() > other.digits.size()) and self.isNegative()));

      For I := self.digits.size() DownTo 1 Do
      begin
        if (self.toDigit(I) < other.toDigit(I)) then
          exit(self.isPositive());

        if (self.toDigit(I) > other.toDigit(I)) then
          exit(self.isNegative());
      end;
    End;

    Function BigInteger.isGreaterThan(var other: BigInteger): Boolean;
    var
      I: Integer;
    Begin
      Result := false;
      if (self.isNeutral() or other.isNeutral()) then
      begin
        if (self.isNeutral()) then
          exit(other.isNegative())
        else
          exit(self.isPositive());
      end;

      if ((sign <> other.sign) and not (self.isNeutral() or other.isNeutral())) then
        exit(self.isPositive());

      if (digits.size() <> other.digits.size()) then
        exit(((self.digits.size() > other.digits.size()) and self.isPositive()) or ((self.digits.size() < other.digits.size()) and self.isNegative()));

      For I := self.digits.size() DownTo 1 Do
      begin
        if (self.toDigit(I) > other.toDigit(I)) then
          exit(self.isPositive());

        if (self.toDigit(I) < other.toDigit(I)) then
          exit(self.isNegative());
      end;
    End;

    Function BigInteger.isLessThanEQ(var other: BigInteger): Boolean;
    Begin
      Result := self.isLessThan(other) or self.isEqualTo(other);
    End;

    Function BigInteger.isGreaterThanEQ(var other: BigInteger): Boolean;
    Begin
      Result := self.isGreaterThan(other) or self.isEqualTo(other);
    End;

    Function BigInteger.isEqualTo(var other: BigInteger): Boolean;
    var
      I: Integer;
    Begin
      Result := true;
      if ((self.sign <> other.sign) or (self.digits.size() <> other.digits.size())) then
        exit(false);

      For I := self.digits.size() DownTo 1 Do
        if (self.toDigit(I) <> other.toDigit(I)) then
          exit(false);
    End;

    Function BigInteger.isNotEqualTo(var other: BigInteger): Boolean;
    Begin
      Result := Not self.isEqualTo(other);
    End;

    Function BigInteger.Add(other: Int64): BigInteger;
    Begin
      Result := self.Add(Result.Init(other));
    End;

    Function BigInteger.Add(var other: BigInteger): BigInteger; overload;
    var
      Carry, Total: Integer;
      I, Len: Integer;
    Begin
      if (other.isNeutral()) then
        exit(self);

      if (@self = @other) then
        exit(self.Multiply(2));

      if (self.sign <> other.sign) then
        exit(self.Subtract(other.Multiply(-1)));

      Result.sign := self.sign;
      Carry := 0; Total := 0; Len := Max(self.digits.size(), other.digits.size());

      For I := 1 To Len Do
      begin
        Total := self.toDigit(I) + other.toDigit(I) + Carry;
        Carry := Total div 10;
        Total := Total mod 10;

        if (I >= Result.digits.size()) then
          SetLength(Result.digits, Result.digits.size() + 1);

        Result.digits[I] := Chr(Total + $30);
      end;

      if (Carry <> 0) then
      begin
        SetLength(Result.digits, Result.digits.size() + 1);
        Result.digits[Result.digits.size()] := Chr(Carry + $30);
      end;
    End;

    Function BigInteger.Subtract(other: Int64): BigInteger;
    Begin
      Result := self.Subtract(Result.Init(other));
    End;

    Function BigInteger.Subtract(var other: BigInteger): BigInteger; overload;
    var
      Borrow, Total: Integer;
      I, Len: Integer;
    Begin
      if (other.isNeutral()) then
        exit(self);

      if (@self = @other) then
        exit(Result.Init(0));

      if (self.sign <> other.sign) then
        exit(self.Add(other.Multiply(-1)));

      if ((self.isPositive() and self.isLessThan(other)) or (self.isNegative() and self.isGreaterThan(other))) then
      begin
        Result := other.Subtract(self);
        Result.sign := 1;
        if (self.isPositive()) then
          Result.sign := -1;
        exit(Result);
      end;

      Result.sign := self.sign;
      Borrow := 0; Total := 0; Len := Max(self.digits.size(), other.digits.size());
      SetLength(Result.digits, Len);

      For I := 1 To Len Do
      Begin
        Total := self.toDigit(I) - other.toDigit(I) - Borrow;
        Borrow := 0;

        if (Total < 0) then
        begin
          Borrow := 1;
          Total += 10;
        end;

        Result.digits[I] := Chr(Total + $30);
      End;

      Result.Normalise();
    End;

    Function BigInteger.Multiply(other: Int64): BigInteger;
    Begin
      Result := self.Multiply(Result.Init(other));
    End;

    Function BigInteger.Multiply(var other: BigInteger): BigInteger; overload;
    var
      I, J: Integer;
      Carry, Total: Integer;
    Begin
      Result.Init(0);
      if (self.isNeutral() or other.isNeutral()) then
        exit(Result);

      Result.sign := 1;
      if (self.sign <> other.sign) then
        Result.sign := -1;

      For J := 0 To other.digits.size() - 1 Do
      begin
        Carry := 0; Total := 0;

        For I := 0 To digits.size() - 1 Do
        begin
          Total := Result.toDigit(I + J + 1) + (self.toDigit(I + 1) * other.toDigit(J + 1)) + Carry;
          Carry := Total div 10;
          Total := Total mod 10;

          if ((I + J + 1) > Result.digits.size()) then
            SetLength(Result.digits, Result.digits.size() + 1);

          Result.digits[I + J + 1] := Chr(Total + $30);
        end;

        if (Carry <> 0) then
        begin
          SetLength(Result.digits, Result.digits.size() + 1);
          Result.digits[Result.digits.size()] := Chr(Carry + $30);
        end;
      end;
    End;

    Function BigInteger.Divide(other: Int64): BigInteger;
    Begin
      Result := self.Divide(Result.Init(other));
    End;

    Function BigInteger.Divide(var Divisor: BigInteger; Remainder: ^BigInteger = nil): BigInteger; overload;
    var
      Rem_Sign: ShortInt;
      Res_Neg: Boolean;
      Dvr: BigInteger;
      Quotient: BigInteger;
      I, Len, Diff, Offset: Integer;
      Borrow, Total: Integer;
    Begin
      if (Divisor.isNeutral()) then
        RaiseException(erDivideByZero, 'Division By Zero Exception');

      Rem_Sign := self.sign;
      Res_Neg := self.sign <> Divisor.sign;

      if (Not self.isNeutral()) then
        Result.sign := 1;

      if (self.isLessThan(Divisor)) then
      begin
        if (Remainder <> nil) then
          Remainder^ := self;
        exit(Result.Init(0));
      end;

      if (@self = @Divisor) then
      begin
        if (Remainder <> nil) then
          Remainder^ := self;
        exit(Result.Init(1));
      end;

      Result.Init(self);
      Dvr.Init(Divisor);
      Quotient.Init(0);

      Dvr.sign := 1;
      Len := Max(Result.digits.size(), Dvr.digits.size());
      Diff := Max(Result.digits.size(), Dvr.digits.size()) - Min(Result.digits.size(), Dvr.digits.size());
      Offset := Len - Diff - 1;

      Result.digits := PadL(Result.digits, Len, '0');
      Dvr.digits := PadL(Dvr.digits, Len, '0');
      Quotient.digits := PadL(Quotient.digits, Len, '0');

      MemMove(Dvr.digits[Diff + 1], Dvr.digits[1], Len - Diff);
      For I := 1 To Diff Do Dvr.digits[I] := '0';

      while (Offset < Len) do
      begin
        while (Result.isGreaterThanEQ(Dvr)) do
        begin
          For I := 1 To Len Do
          Begin
            Total := Result.toDigit(I) - Dvr.toDigit(I) - Borrow;
            Borrow := 0;

            if (Total < 0) then
            begin
              Borrow := 1;
              Total += 10;
            end;

            Result.digits[I] := Chr(Total + $30);
          End;
          Inc(Quotient.digits[Len - Offset]);
        end;

        if ((Remainder <> nil) and (Offset = (Len - 1))) then
        begin
          Remainder^ := Result;
          Remainder^.sign := Rem_Sign;
          Remainder^.Normalise();
          if (Remainder = @self) then
            exit(Result);
        end;

        MemMove(Dvr.digits[2], Dvr.digits[1], Len - 1);
        Dvr.digits[Len] := '0';
        Inc(Offset);
      end;

      Quotient.sign := 1;
      if (Res_Neg) then
        Quotient.sign := -1;

      Quotient.Normalise();
      Result := Quotient;
    End;

    Function BigInteger.Modulo(var other: BigInteger): BigInteger;
    Begin
      self.Divide(other, @Result);
    End;



    Test case:

    Simba Code:
    var
      A, B: BigInteger;
    begin
      ClearDebug();

      A.Init('123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789');
      B.Init('5678901234567890123456789');

      writeln(A.Multiply(B));
      writeln(A.Divide(B));
      writeln(A.Modulo(B));
      writeln(A.Add(B));
      writeln(A.Subtract(B));

      writeln(A.Add(B.Multiply(A).Divide(B))); //Chaining.
    end.

    Result:

    Progress Report:
    701098911537997408300588491020579849102057984910205798491020579849102057984910205798491020579849101987875019051998750190521
    
    21739555578261356323493334462240019404063213093086385865664001138064832939
    
    229383133009231653083918
    
    123456789012345678901234567890123456789012345678901234567890123456789012351357802469135780246913578
    
    123456789012345678901234567890123456789012345678901234567890123456789012340000000000000000000000000
    
    246913578024691357802469135780246913578024691357802469135780246913578024691357802469135780246913578



    If Lape had operator overloading, it's be nice because then you could get rid of all the annoying functions and just do BigInteger *+/-%, etc.. instead of Multiply, Add, Subtract, Modulo, etc..

    Anyway, Enjoy..
    Last edited by Brandon; 02-04-2015 at 03:41 AM.
    I am Ggzz..
    Hackintosher

  2. #2
    Join Date
    Sep 2010
    Posts
    5,762
    Mentioned
    136 Post(s)
    Quoted
    2739 Post(s)

    Default

    Nice! Today I was thinking to myself how > 64 bit integers could be handled in simba and I was like "well I guess you could have to pass it to the plugin (another language that has support for higher numbers?) as a string and get the result back as a string"

    Never thought it could be done with simba itself, nice

  3. #3
    Join Date
    Feb 2012
    Location
    Wonderland
    Posts
    1,988
    Mentioned
    41 Post(s)
    Quoted
    272 Post(s)

    Default

    Project Listing++
    big integer lib fun

  4. #4
    Join Date
    Feb 2006
    Location
    Australia
    Posts
    628
    Mentioned
    15 Post(s)
    Quoted
    105 Post(s)

    Default

    Great thread Brandon, thanks for posting it! I'd rep again if I could

  5. #5
    Join Date
    Sep 2008
    Location
    Not here.
    Posts
    5,422
    Mentioned
    13 Post(s)
    Quoted
    242 Post(s)

    Default

    This is a cool implementation.

    Got me curious about some built-in bignums.

    Golangs is sweet https://golang.org/src/math/big/nat.go

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •