January 26, 2021, 05:13:56 AM

Author Topic: [bmx] Infinitely Large +/- Ints by Spencer [ 1+ years ago ]  (Read 418 times)

Offline BlitzBot

  • Jr. Member
  • **
  • Posts: 1
Title : Infinitely Large +/- Ints
Author : Spencer
Posted : 1+ years ago

Description : My first attempt at adding and subtracting arbitrarily large positive and negative integers. I am sure it could use some fine tuning. However, it can give you the exact value of 2^768 (more than 230 digits long!! At least i am pretty sure... The Windows XP calculator doesn't show me every digit, so I cannot verify the value exactly)

Code :
Code: BlitzMax
  1. ' Examples Calculating Very Large numbers with Type Inf                                                                
  2. '                                                                                                                      
  3. '      CREATED: MARCH 11, 2009                                                                                          
  4.                                                                                
  5. ' TERMS OF USE: Any person/entity can use this code. Note that it's a work in prog.                                    
  6. '              (a little credit would be nice too!) ;)                                                                  
  7. '____________________________________________________________________________________                                  
  8.                                                                                                                        
  9.     Global A:String                                                                                                    
  10.     Global B:String                                                                                                    
  11.     Global C:String                                                                                                    
  12.                                                                                                                        
  13.     A = "-1000000000000000000000000000000000000"                                                                        
  14.     B = "+                         00000 001233"                                                                        
  15.     'NOTE: "+" sign is always optional.                                                                                
  16.     'NOTE: spaces and leading zeros are ignored                                                                        
  17.                                                                                                                        
  18.     Print Inf.Add(A,B)                                                                                                  
  19.     Print Inf.Sub(A,B)                                                                                                  
  20.                                                                                                                        
  21.     '---------------------------------------------------------------                                                    
  22.     ' what is 2^768 ?                                                                                                  
  23.                                                                                                                        
  24.     A = "2" ' 2^1 = 2                                                                                                  
  25.                                                                                                                        
  26.     For x = 2 To 768                                                                                                    
  27.                                                                                                                        
  28.         A = Inf.Add(A,A)                                                                                                
  29.         Print "2^"+(x+1) + " = " + A                                                                                    
  30.                                                                                                                        
  31.     Next                                                                                                                
  32.     '---------------------------------------------------------------                                                    
  33.                                                                                                                        
  34.     '---------------------------------------------------------------                                                    
  35.     'can be used as an Object too                                                                                      
  36.                                                                                                                        
  37.         Global Atype:Inf = New INf                                                                                      
  38.         Atype.Value = "-1000000000000000000000"                                                                        
  39.         Atype.Plus(B)                                                                                                  
  40.         Print "FROM AType.Value=" + Atype.Value                                                                        
  41.         Atype = Null                                                                                                    
  42.                                                                                                                        
  43.     '---------------------------------------------------------------                                                    
  44.                                                                                                                        
  45.     GCCollect()                                                                                                        
  46.                                                                                                                        
  47. '*******************************************************************************************************                
  48. '*                                                                                                    '*                
  49. '*******************************************************************************************************                
  50. '*     TYPE: Inf                                                                                      '*                
  51. '*  PURPOSE: Calculate the addition and subtraction of (n)-digit long positive and negative integers  '*                
  52. '*           Functional applications include high score counters and monetary values.                 '*                
  53. '*  CREATED: MARCH 11, 2009                                                                           '*                
  54. '*                           (USA)                                                                    '*                
  55. '*                                                                                                    '*                
  56. '*  TERMS OF USE: Any person/entity can use this code. (a little credit would be nice too!) ;)        '*                
  57. '*          NOTE: It's a work in progress.                                                            '*                
  58. '*******************************************************************************************************                
  59. Type Inf                                                                                              '*                
  60.                                                                                                       '*                
  61.     Field Value:String                                                                                '*                
  62.                                                                                                       '*                
  63.     '-----------------------------------------------------------                                      '*                
  64.      Method Plus(ValueToAdd:String)                                                                   '*                
  65.         Value = Inf.Add(Value,ValueToAdd)                                                             '*                
  66.      End Method                                                                                       '*                
  67.     '-----------------------------------------------------------                                      '*                
  68.                                                                                                       '*                
  69.     '-----------------------------------------------------------                                      '*                
  70.      Method Minus(ValueToSubtract:String)                                                             '*                
  71.         Value = Inf.Sub(Value,ValueToSubtract)                                                        '*                
  72.      End Method                                                                                       '*                
  73.     '-----------------------------------------------------------                                      '*                
  74.                                                                                                       '*                
  75.     '--------------------------------------------------------------------------------                 '*                
  76.     Function Add:String(Value1:String,Value2:String)                                                  '*                
  77.         Return Replace(Inf.FormatValue(Inf.Calculate("+",Value1,Value2)),"+","")                      '*                
  78.     End Function                                                                                      '*                
  79.     '--------------------------------------------------------------------------------                 '*                
  80.                                                                                                       '*                
  81.     '--------------------------------------------------------------------------------                 '*                
  82.     Function Sub:String(Value1:String,Value2:String)                                                  '*                
  83.         Return Replace(Inf.FormatValue(Inf.Calculate("-",Value1,Value2)),"+","")                      '*                
  84.     End Function                                                                                      '*                
  85.     '--------------------------------------------------------------------------------                 '*                
  86.                                                                                                       '*                
  87.                                                                                                       '*                
  88.     '--------------------------------------------------------------------------------                 '*                
  89.     Function Calculate:String(Opperator:String, Value1:String, Value2:String)                         '*                
  90.                                                                                                       '*                
  91.         Local Result   : String                                                                       '*                
  92.         Local Sign1    : String                                                                       '*                
  93.         Local Sign2    : String                                                                       '*                
  94.         Local SignCombo: String                                                                       '*                
  95.                                                                                                       '*                
  96.         Value1 = FormatValue(Value1)                                                                  '*                
  97.         Value2 = FormatValue(Value2)                                                                  '*                
  98.                                                                                                       '*                
  99.         Sign1 = Left(Value1,1)                                                                        '*                
  100.         Sign2 = Left(Value2,1)                                                                        '*                
  101.                                                                                                       '*                
  102.         SignCombo = Sign1+Opperator+Sign2                                                             '*                
  103.                                                                                                       '*                
  104.         Value1 = Right(Value1,Value1.Length-1)                                                        '*                
  105.         Value2 = Right(Value2,Value2.Length-1)                                                        '*                
  106.                                                                                                       '*                
  107.         Select SignCombo                                                                              '*                
  108.                                                                                                       '*                
  109.             Case "+++"                                                                                '*                
  110.                 Result = Inf.InternalAdditionFunction(Value1,Value2)                                  '*                
  111.                                                                                                       '*                
  112.             Case "-++"                                                                                '*                
  113.                 Result = Inf.InternalSubtractionFunction(Value2,Value1)                               '*                
  114.             Case "++-"                                                                                '*                
  115.                 Result = Inf.InternalSubtractionFunction(Value1,Value2)                               '*                
  116.             Case "-+-"                                                                                '*                
  117.                 Result = "-" + Inf.InternalAdditionFunction(Value1,value2)                            '*                
  118.             Case "+-+"                                                                                '*                
  119.                 Result = Inf.InternalSubtractionFunction(Value1,Value2)                               '*                
  120.                                                                                                       '*                
  121.             Case "--+"                                                                                '*                
  122.                 Result = "-" + Inf.InternalAdditionFunction(Value1,value2)                            '*                
  123.             Case "+--"                                                                                '*                
  124.                 Result =  Inf.InternalAdditionFunction(Value1,value2)                                 '*                
  125.                                                                                                       '*                
  126.             Case "---"                                                                                '*                
  127.                 Result = Inf.InternalSubtractionFunction(Value2,Value1)                               '*                
  128.                                                                                                       '*                
  129.         End Select                                                                                    '*                
  130.                                                                                                       '*                
  131.         Return Result                                                                                 '*                
  132.                                                                                                       '*                
  133.     End Function                                                                                      '*                
  134.     '--------------------------------------------------------------------------------                 '*                
  135.                                                                                                       '*                
  136.     '--------------------------------------------------------------------------------                 '*                
  137.     Function InternalAdditionFunction:String(Value1:String, Value2:String)                            '*                
  138.                                                                                                       '*                
  139.         Value1 = "0" + Value1                                                                         '*                
  140.         Value2 = "0" + Value2                                                                         '*                
  141.                                                                                                       '*                
  142.         While Value1.Length < Value2.Length                                                           '*                
  143.             Value1 = "0" + Value1                                                                     '*                
  144.         Wend                                                                                          '*                
  145.                                                                                                       '*                
  146.         While Value2.Length < Value1.Length                                                           '*                
  147.             Value2 = "0" + Value2                                                                     '*                
  148.         Wend                                                                                          '*                
  149.                                                                                                       '*                
  150.         Local TempDecimalPlace : Int                                                                  '*                
  151.         Local DecimalPlaces    : Int                                                                  '*                
  152.         Local CarryValue       : Byte                                                                 '*                
  153.         Local Digit            : Byte                                                                 '*                
  154.         Local DigitToAdd       : Byte                                                                 '*                
  155.         Local DigitSum         : Byte                                                                 '*                
  156.         Local Result           : String                                                               '*                
  157.                                                                                                       '*                
  158.         DecimalPlaces = Value1.Length                                                                 '*                
  159.                                                                                                       '*                
  160.         For TempDecimalPlace = DecimalPlaces To 1 Step -1                                             '*                
  161.                                                                                                       '*                
  162.             Digit      = Int(Mid(Value1 ,TempDecimalPlace ,1))                                        '*                
  163.             DigitToAdd = Int(Mid(Value2,TempDecimalPlace ,1))                                         '*                
  164.             DigitSum   = Digit + DigitToAdd + CarryValue                                              '*                
  165.                                                                                                       '*                
  166.             If DigitSum > 9 Then                                                                      '*                
  167.                 CarryValue = 1                                                                        '*                
  168.             Else                                                                                      '*                
  169.                 CarryValue = 0                                                                        '*                
  170.             EndIf                                                                                     '*                
  171.                                                                                                       '*                
  172.             Result = Right(String(DigitSum),1) + Result                                               '*                
  173.         Next                                                                                          '*                
  174.                                                                                                       '*                
  175.         If Left(Result,1) = "0" Then                                                                  '*                
  176.             Return Right(Result,Len(Result)-1)                                                        '*                
  177.         Else                                                                                          '*                
  178.             Return Result                                                                             '*                
  179.         EndIf                                                                                         '*                
  180.                                                                                                       '*                
  181.     End Function                                                                                      '*                
  182.     '--------------------------------------------------------------------------------                 '*                
  183.                                                                                                       '*                
  184.     '--------------------------------------------------------------------------------                 '*                
  185.     'REF: http://en.wikipedia.org/wiki/Ten%27s_complement                                             '*                
  186.      Function GetTensComplement:String(Value:String)                                                  '*                
  187.                                                                                                       '*                
  188.         Local Complement  : String                                                                    '*                
  189.         Local TempDigit   : Byte                                                                      '*                
  190.         Local TempRadix   : Byte                                                                      '*                
  191.         Local Decimals    : Int                                                                       '*                
  192.                                                                                                       '*                
  193.         Decimals = Value.Length                                                                       '*                
  194.                                                                                                       '*                
  195.         For Local TempDecimal:Int = Decimals To 1 Step -1                                             '*                
  196.                                                                                                       '*                
  197.             TempDigit  = Int(Mid(Value,TempDecimal,1))                                                '*                
  198.             TempRadix  = 9 - TempDigit                                                                '*                
  199.             Complement = String(TempRadix) + Complement                                               '*                
  200.                                                                                                       '*                
  201.         Next                                                                                          '*                
  202.                                                                                                       '*                
  203.         Return Complement                                                                             '*                
  204.                                                                                                       '*                
  205.     End Function                                                                                      '*                
  206.     '--------------------------------------------------------------------------------                 '*                
  207.                                                                                                       '*                
  208.                                                                                                       '*                
  209.     '--------------------------------------------------------------------------------                 '*                
  210.     Function InternalSubtractionFunction:String(Value1:String, Value2:String)                         '*                
  211.                                                                                                       '*                
  212.         Local TempValue            : String                                                           '*                
  213.         Local Value1Digit          : Int                                                              '*                
  214.         Local Value2Digit          : Int                                                              '*                
  215.         Local ValuesAreEqual       : Byte = False                                                     '*                
  216.         Local ResultWillBeNegative : Byte = False                                                     '*                
  217.         Local Result               : String                                                           '*                
  218.                                                                                                       '*                
  219.         If Value2.Length > Value1.Length Then                                                         '*                
  220.                                                                                                       '*                
  221.             TempValue = Value1                                                                        '*                
  222.             Value1 = Value2                                                                           '*                
  223.             Value2 = TempValue                                                                        '*                
  224.             ResultWillBeNegative = True                                                               '*                
  225.                                                                                                       '*                
  226.         ElseIf Value2.Length = Value1.Length  Then                                                    '*                
  227.                                                                                                       '*                
  228.             ValuesAreEqual = True                                                                     '*                
  229.                                                                                                       '*                
  230.             For Local CurrentDigitPos = 1 To Value2.Length Step 1                                     '*                
  231.                                                                                                       '*                
  232.                 Value1Digit = Int(Mid(Value1,CurrentDigitPos,1))                                      '*                
  233.                 Value2Digit = Int(Mid(Value2,CurrentDigitPos,1))                                      '*                
  234.                                                                                                       '*                
  235.                 If Value1Digit > Value2Digit Then                                                     '*                
  236.                                                                                                       '*                
  237.                     ValuesAreEqual = False                                                            '*                
  238.                     Exit 'For Loop                                                                    '*                
  239.                                                                                                       '*                
  240.                 ElseIf Value2Digit > Value1Digit Then                                                 '*                
  241.                                                                                                       '*                
  242.                     ValuesAreEqual = False                                                            '*                
  243.                     TempValue = Value1                                                                '*                
  244.                     Value1 = Value2                                                                   '*                
  245.                     Value2 = TempValue                                                                '*                
  246.                     ResultWillBeNegative = True                                                       '*                
  247.                     Exit 'For Loop                                                                    '*                
  248.                                                                                                       '*                
  249.                 EndIf                                                                                 '*                
  250.                                                                                                       '*                
  251.             Next                                                                                      '*                
  252.                                                                                                       '*                
  253.             If ValuesAreEqual Then                                                                    '*                
  254.                                                                                                       '*                
  255.                 Return "0"                                                                            '*                
  256.                                                                                                       '*                
  257.             EndIf                                                                                     '*                
  258.                                                                                                       '*                
  259.         EndIf                                                                                         '*                
  260.                                                                                                       '*                
  261.                                                                                                       '*                
  262.         While Value1.Length < Value2.Length                                                           '*                
  263.             Value1 = "0" + Value1                                                                     '*                
  264.         Wend                                                                                          '*                
  265.                                                                                                       '*                
  266.         While Value2.Length < Value1.Length                                                           '*                
  267.             Value2 = "0" + Value2                                                                     '*                
  268.         Wend                                                                                          '*                
  269.                                                                                                       '*                
  270.         Local TensComplement:String = Inf.GetTensComplement(Value2)                                   '*                
  271.                                                                                                       '*                
  272.         Result = Inf.Add(Value1, TensComplement)                                                      '*                
  273.         Result = Inf.Add(Result,"1")                                                                  '*                
  274.                                                                                                       '*                
  275.         If Int(Left(Result,1)) > 1 Then                                                               '*                
  276.                                                                                                       '*                
  277.             Result = String(Int(Left(Result,1))-1) + Right(Result,Result.Length-1)                    '*                
  278.         Else                                                                                          '*                
  279.             Result = Right(Result,Result.Length-1)                                                    '*                
  280.                                                                                                       '*                
  281.         EndIf                                                                                         '*                
  282.                                                                                                       '*                
  283.                                                                                                       '*                
  284.         If ResultWillBeNegative Then                                                                  '*                
  285.                                                                                                       '*                
  286.             Result = "-" + Result                                                                     '*                
  287.                                                                                                       '*                
  288.         EndIf                                                                                         '*                
  289.                                                                                                       '*                
  290.         Return Result                                                                                 '*                
  291.                                                                                                       '*                
  292.     End Function                                                                                      '*                
  293.     '--------------------------------------------------------------------------------                 '*                
  294.                                                                                                       '*                
  295.     '--------------------------------------------------------------------------------                 '*                
  296.     Function FormatValue:String(Value:String)                                                         '*                
  297.                                                                                                       '*                
  298.         Local ReturnValue  : String                                                                   '*                
  299.         Local CurrentDigit : String                                                                   '*                
  300.         Local ValueSign    : String                                                                   '*                
  301.         Local TempPosition : Int                                                                      '*                
  302.                                                                                                       '*                
  303.         Value = Trim(Value)                                                                           '*                
  304.                                                                                                       '*                
  305.         If Left(Value,1) = "-" Then                                                                   '*                
  306.                                                                                                       '*                
  307.             ValueSign = "-"                                                                           '*                
  308.             Value = Right(Value,Value.Length-1)                                                       '*                
  309.                                                                                                       '*                
  310.         ElseIf Left(Value,1) = "+" Then                                                               '*                
  311.                                                                                                       '*                
  312.             ValueSign = "+"                                                                           '*                
  313.             Value = Right(Value,Value.Length-1)                                                       '*                
  314.         Else                                                                                          '*                
  315.                                                                                                       '*                
  316.             ValueSign = "+"                                                                           '*                
  317.         EndIf                                                                                         '*                
  318.                                                                                                       '*                
  319.         TempPosition = 1                                                                              '*                
  320.                                                                                                       '*                
  321.         While Mid(Value,TempPosition,1)="0"                                                           '*                
  322.                                                                                                       '*                
  323.             Value = Right(Value,Value.Length-(TempPosition-1))                                        '*                
  324.             TempPosition = TempPosition + 1                                                           '*                
  325.                                                                                                       '*                
  326.         Wend                                                                                          '*                
  327.                                                                                                       '*                
  328.         For Local DigitPosition = 1 To Value.Length Step 1                                            '*                
  329.                                                                                                       '*                
  330.             CurrentDigit = Mid(Value,DigitPosition,1)                                                 '*                
  331.                                                                                                       '*                
  332.             Select CurrentDigit                                                                       '*                
  333.                                                                                                       '*                
  334.                 Case "0","1","2","3","4","5","6","7","8","9"                                          '*                
  335.                     ReturnValue = ReturnValue + CurrentDigit                                          '*                
  336.                 Default                                                                               '*                
  337.                     ReturnValue = ReturnValue + "0"                                                   '*                
  338.                                                                                                       '*                
  339.             End Select                                                                                '*                
  340.                                                                                                       '*                
  341.         Next                                                                                          '*                
  342.                                                                                                       '*                
  343.         ReturnValue = ValueSign + ReturnValue                                                         '*                
  344.                                                                                                       '*                
  345.         Return ReturnValue                                                                            '*                
  346.                                                                                                       '*                
  347.     End Function                                                                                      '*                
  348.     '--------------------------------------------------------------------------------                 '*                
  349.                                                                                                       '*                
  350. End Type                                                                                              '*                
  351. '*******************************************************************************************************                
  352. '*End of Type Inf                                                                                     '*                
  353. '*                                                                                                    '*                
  354. '*                                                                                                    '*                
  355. '*                                                                                                    '*                
  356. '*                                                                                                    '*                
  357. '*                                                                                                    '*                
  358. '*******************************************************************************************************


Comments :


Nate the Great(Posted 1+ years ago)

 Great code.  I seem to have found a bug despite how reliable it seems though.  Try inf.sub("11900","11800") and you get... "00" instead of "100" like you should.  Unfortunately I cannot understand a bit of this code so I have no idea what is causing the bug or I would fix it myself.  Is there anyone familiar with parsers/string addition that could help?edit: sorry for the bump, didn't realize this was 2 yrs old


Spencer(Posted 1+ years ago)

 @[Nate the Great] No worries Nate! its been a while since I've been on. I re-wrote the functions and i'm pretty sure i've removed the error. I posted the update in the Code Archives under Algorithms.  The new functions only handle positive values. New Version: <a href="codearcs0b47.html?code=2891" target="_blank">http://www.blitzbasic.com/codearcs/codearcs.php?code=2891[/url]


 

SimplePortal 2.3.6 © 2008-2014, SimplePortal