Android Question I Need Sub Code that Can Compute Large and Very Large Exponential

omo

Active Member
Licensed User
Longtime User
I need b4x code that can compute large and very large exponential like 3^935687429879864897 or more. Answer to this sample should be: 2.19222399769E+446436360569697305

I have tried different methods and algorithms to no effect. I also tried some AI, but couldn't get right code with stable solution.

I tried also to use Bigdecimal library in the forum, once the exponent digits is more than 5 or 6, the app hangs and force to restart. Try and catch couldn't solve it either.

If your solution can solve this even if it is using java object in b4x or bigdecimals in b4x ( in case I didn't use it well) or other algorithms, I don't mind. So far your solution can solve this and more:

3^935687429879864897 and get this result: 2.19222399769E+446436360569697305 or close to it.
Then, your solution should be ok and robust enough to handle more or less

Thank you in advance
 
Last edited:
Solution
Here another example.

B4X pages project using this library with Inline Java. Tested with B4J.

The result: 2.19222399769E+446436360569697305

Copy big-math-2.3.2.jar to the B4J additional libraries folder.

B4X:
Sub Class_Globals
    Private Root As B4XView
    Private xui As XUI
    ' Inline Java object
    Private joInlineJava As JavaObject = Me
End Sub

Public Sub Initialize
'    B4XPages.GetManager.LogEvents = True
End Sub

'This event will be called once, before the page becomes visible.
Private Sub B4XPage_Created (Root1 As B4XView)
    Root = Root1
    Root.LoadLayout("MainPage")
End Sub

Private Sub Button1_Click
    ' Example: compute 3^935687429879864897 with 12 digits
    Dim result As String
    result =...

emexes

Expert
Licensed User
Longtime User
The modified Subs:

B4X:
Sub MaxInt(N1 As Int, N2 As Int) As Int
    If N1 > N2 Then
        Return N1
    Else
        Return N2
    End If
End Sub

Sub GetDigitAt(S As String, I As Int) As Int
    Dim LastChar As Int = S.Length - 1
    If I > LastChar Then Return 0
    Return Asc(S.CharAt(I)) - 48
End Sub

Sub GetDigitAtReverse(S As String, I As Int) As Int
    Dim LastChar As Int = S.Length - 1
    If I > LastChar Then Return 0
    Return Asc(S.CharAt(LastChar - I)) - 48
End Sub

Sub AddStrings(N1 As String, N2 As String) As String
    Dim Result As String
    Dim Carry As Int

    For I = 0 To MaxInt(N1.Length, N2.Length) - 1
        Dim Sum As Int = GetDigitAtReverse(N1, I) + GetDigitAtReverse(N2, I) + Carry

        Carry = 0
        Do While Sum > 9
            Sum = Sum - 10
            Carry = Carry + 1
        Loop

        Result = Sum & Result
    Next
    
    If Carry <> 0 Then
        Result = Carry & Result
    End If
    
    Return Result
End Sub

Sub RemoveLeadingZeroes(N As String) As String
    Do While N.Length > 1
        If N.CharAt(0) <> "0" Then Exit
        N = N.SubString(1)
    Loop
    Return N
End Sub

Sub ShiftRightString(N As String) As String
    Dim Result As String
    Dim Carry As Int
    For I = 0 To N.Length - 1
        Dim Temp As Int = Carry * 10 + GetDigitAt(N, I)
        Carry = Bit.And(Temp, 1)
        Result = Result & Bit.ShiftRight(Temp, 1)
    Next
    
    Return RemoveLeadingZeroes(Result)
End Sub

Sub MultiplyStrings(N1 As String, N2 As String) As String
    Dim ResultSize As Int = N1.Length + N2.Length
    Dim P(ResultSize) As Int
    
    For I1 = 0 To N1.Length - 1
        Dim D1 As Int = GetDigitAtReverse(N1, I1)
        For I2 = 0 To N2.Length - 1
            Dim D2 As Int = GetDigitAtReverse(N2, I2)
            P(I1 + I2) = P(I1 + I2) + D1 * D2
        Next
        
        For I = 0 To ResultSize - 2
            Do While P(I) > 9
                P(I) = P(I) - 10
                P(I + 1) = P(I + 1) + 1
            Loop
        Next
    Next
    
    Dim Result As String
    For I = 0 To ResultSize - 1
        Result = P(I) & Result
    Next
    
    Return RemoveLeadingZeroes(Result)
End Sub

Sub MultiplyStrings2(N1() As String, N2() As String) As String()
    Dim Result(2) As String
    
    Result(0) = MultiplyStrings(N1(0), N2(0))
    Result(1) = AddStrings(N1(1), N2(1))

    Return Result   
End Sub

Sub Commas(N As String) As String
    For I = N.Length - 3 To 1 Step -3
        N = N.SubString2(0, I) & "," & N.SubString(I)
    Next
    Return N
End Sub

Sub RandomNumber(L As Int) As String
    Dim Result As String = Rnd(1, 10)
    For I = 2 To L
        Result = Result & Rnd(0, 10)
    Next   
    Return Result
End Sub

Sub LimitString(N As String, L As Int) As String
    If L > 0 Then
        If N.Length > L Then
            N = N.SubString2(0, L + 1)
            N = AddStrings(N, "5")
            N = N.SubString2(0, L)
        End If
    End If
    Return N
End Sub

Sub LimitString2(N() As String, L As Int) As String()
    If L > 0 Then
        If N(0).Length > L Then
            Dim NumDigitsToRemove As Int = N(0).Length - L
            N(0) = LimitString(N(0), L)
            N(1) = AddStrings(N(1), NumDigitsToRemove.As(String))
        End If
    End If
    
    Return N
End Sub

Sub PowerStrings(Base As String, Exponent As String, LimitLength As Int) As String()
    Dim GuardLength As Int = 16
    
    Dim Result() As String = Array As String("1", "0")
    Dim Term() As String = Array As String(Base, "0")
    
    Do While Exponent <> "0"
        If Bit.And(GetDigitAtReverse(Exponent, 0), 1) <> 0 Then
            Result = MultiplyStrings2(Result, Term)
            Result = LimitString2(Result, LimitLength + GuardLength)
        End If
        
        Exponent = ShiftRightString(Exponent)
        If Exponent = "0" Then Exit

        Term = MultiplyStrings2(Term, Term)
        Term = LimitString2(Term, LimitLength + GuardLength)
    Loop
    Return LimitString2(Result, LimitLength)
End Sub

Sub ScientificFormat(N() As String) As String
    If N(1) = "0" Then Return Commas(N(0))

    Dim Mantissa As String = N(0)
    Dim Exponent As String = N(1)
    
    If Mantissa.Length > 1 Then
        Dim NumDigitsAfterPoint As String = Mantissa.Length - 1
        Exponent = AddStrings(Exponent, NumDigitsAfterPoint)
        Mantissa = Mantissa.CharAt(0) & "." & Mantissa.SubString(1)       
    End If
    
    Return Mantissa & "E+" & Exponent
End Sub

and associated test code:

B4X:
If False Then
    Log("Power" & TAB & "Digits" & TAB & "Value")
    For I = 1 To 100000 Step 73
        Dim T1 As Long = DateTime.now
        Dim Temp() As String = PowerStrings("3", I, 80)
        Dim T2 As Long = DateTime.now
        Log((T2 - T1) & TAB & I & TAB & Temp(0).Length & TAB & ScientificFormat(Temp))
    Next
End If

If True Then
    Dim B As String = "3"
    Dim E As String = "935687429879864897"
    Dim B As String = "23675"
    Dim E As String = "627423852959"
    Log("MaxDig" & TAB & "Value")
    For LimitLength = 3 To 1000 Step 73
        Dim Temp() As String = PowerStrings(B, E, LimitLength)
        Log(LimitLength & TAB & ScientificFormat(Temp))
    Next
End If
 
Upvote 0

emexes

Expert
Licensed User
Longtime User
All numbers are zero or positive, ie non-negative.

Plain decimal integers are stored as a string of digits, ideally with no leading zeros except for 0 itself.

Scientific-format numbers are stored as an array of two strings: the first element (0) is the integer mantissa, and the second element (1) is the exponent, ie the number of zeros after the mantissa, thus ["2998", "5"] would be the number 299800000

Again, the routines don't handle negative numbers, nor do they handle fractional values. Definitely non-negative integers only.

The only limits are memory and time. Exponents can be > 2^64 no problem. Come to think of it, can probably handle a googleplex.
 
Reactions: omo
Upvote 0

omo

Active Member
Licensed User
Longtime User
Whaoo! Welldone, @emexes; I wasn't even expecting you will complete it as fast as this. Thank you so much. This is really good for even very large cases. I will cool down to study and digest this code. My only fear as you earlier pointed out is that of speed in case of dealing with very large user entries. However, it will fit other areas of applications and the methodologies will be studied. Thank you so much for your precious and golden time. I really appreciate
 
Upvote 0

emexes

Expert
Licensed User
Longtime User
speed in case of dealing with very large user entries.

It's not the value of the numbers that is a problem, but the number of digits that are involved, ie the precision.

For example, to calculate 3^4096 doesn't need 4095 multiplications, it only needs 12 multiplications.

Likewise, to calculate your first example 3^935687429879864897 doesn't need 935687429879864896 multiplications, it only needs 89 multiplications:

Exponentiation multiplications, starting with Result = 1 and Term = 3:
Result 3^1                          (3^0 * 3^1)
Term   3^2       (3^1 * 3^1)
Term   3^4       (3^2 * 3^2)
Term   3^8       (3^4 * 3^4)
Term   3^16      (3^8 * 3^8)
Term   3^32      (3^16 * 3^16)
Term   3^64      (3^32 * 3^32)
Result 3^65                         (3^1 * 3^64)
Term   3^128     (3^64 * 3^64)
Term   3^256     (3^128 * 3^128)
Term   3^512     (3^256 * 3^256)
Result 3^577                        (3^65 * 3^512)
Term   3^1024    (3^512 * 3^512)
Result 3^1601                       (3^577 * 3^1024)
Term   3^2048    (3^1024 * 3^1024)
Result 3^3649                       (3^1601 * 3^2048)
Term   3^4096    (3^2048 * 3^2048)
Result 3^7745                       (3^3649 * 3^4096)
Term   3^8192
Term   3^16384
Term   3^32768
Result 3^40513
Term   3^65536
Result 3^106049
Term   3^131072
Term   3^262144
Term   3^524288
Result 3^630337
Term   3^1048576
Term   3^2097152
Term   3^4194304
Result 3^4824641
Term   3^8388608
Result 3^13213249
Term   3^16777216
Term   3^33554432
Result 3^46767681
Term   3^67108864
Result 3^113876545
Term   3^134217728
Result 3^248094273
Term   3^268435456
Term   3^536870912
Term   3^1073741824
Term   3^2147483648
Result 3^2395577921
Term   3^4294967296
Term   3^8589934592
Result 3^10985512513
Term   3^17179869184
Term   3^34359738368
Term   3^68719476736
Term   3^137438953472
Term   3^274877906944
Result 3^285863419457
Term   3^549755813888
Result 3^835619233345
Term   3^1099511627776
Term   3^2199023255552
Result 3^3034642488897
Term   3^4398046511104
Term   3^8796093022208
Result 3^11830735511105
Term   3^17592186044416
Result 3^29422921555521
Term   3^35184372088832
Result 3^64607293644353
Term   3^70368744177664
Term   3^140737488355328
Term   3^281474976710656
Term   3^562949953421312
Term   3^1125899906842624
Result 3^1190507200486977
Term   3^2251799813685248
Result 3^3442307014172225
Term   3^4503599627370496
Result 3^7945906641542721
Term   3^9007199254740992
Result 3^16953105896283713
Term   3^18014398509481984
Result 3^34967504405765697
Term   3^36028797018963968
Result 3^70996301424729665
Term   3^72057594037927936
Term   3^144115188075855872
Term   3^288230376151711744
Result 3^359226677576441409
Term   3^576460752303423488    eg = (previous) Term * itself
Result 3^935687429879864897    eg = (previous) Result * Term
 
Last edited:
Reactions: omo
Upvote 0

omo

Active Member
Licensed User
Longtime User
...Likewise, to calculate your first example 3^935687429879864897 doesn't need 935687429879864896 multiplications, it only needs 89 multiplications
Ok, that's cool, I will do some test cases; speed even be nearly the same
 
Upvote 0

emexes

Expert
Licensed User
Longtime User
3^935687429879864897

I think the reason that you initially found problems when calculating this, is that the Java BigInteger can only handle numbers as large as can be represented by a memory address eg absolute maximums of Log10(2) * 2^32 * 8 = 10,343,311,891 decimal digits for a 32-bit address and Log10(2) * 2^64 * 8 = 44,424,186,308,186,857,058 decimal digits for a 64-bit address.

And then the standard BigDecimal adds another 2^31-1 digit places with its 32-bit scale.


Apparently there are BigDecimal libraries with 64-bit scales, which would add another 2^63-1 digit places, getting you up to around 1E+9223372036854775808 which with its 19-digit exponent can handle your example 18 digit exponent:

2.19222399769E+446436360569697305

but not by much.

Whereas my routines use a BigInteger(-like) for the exponent as well as the mantissa, so if you need a 30-digit or 130-digit or 1300-digit exponent instead of a miniscule 19-digit exponent, then that should be no problem.
 
Reactions: omo
Upvote 0

emexes

Expert
Licensed User
Longtime User
Out of interest, how did you calculate your example result of:

2.19222399769E+446436360569697305

? because as we discovered early on, Java's Doubles aren't good enough for the job, even if we work around the range limit by using logarithms.

BigDecimal could get you as close as approximately however many digits accurate its logarithm and power functions are, less however many digits are in the exponent of the result.
 
Last edited:
Reactions: omo
Upvote 0

omo

Active Member
Licensed User
Longtime User
You are right. Although, I have even modified that java code a bit to handle big decimal for base and bigdecimal for exponent since I found it having issues with decimal point entries at the exponent and to integrate well with my existing system. So, is working fine since then.
 
Upvote 0

omo

Active Member
Licensed User
Longtime User
Before I modified that java code, I was not having problem calculating this 3^935687429879864897, but I had problem calculating this 2.19222399769E+446436360569697305 and other with decimal point. So, I had to modify it to accept bigdecimal at both base and exponent, and has been working fine so far handling with and without decimal entries
 
Upvote 0

omo

Active Member
Licensed User
Longtime User
"...Apparently there are BigDecimal libraries with 64-bit scales, which would add another 2^63-1 digit places, getting you up to around 1E+9223372036854775808 which with its 19-digit exponent can handle your example 18 digit exponent..."

As you said and quoted above, does that suggest bigdecimal (java) used in that math class is 64 bits that first solved my problem while the one of b4x library bignumber I am using is a standard 32 bits while it struggles to handle those 18 and 19-digits exponent?

But why I doubt if bignumber library (b4x version) is 32-bits is that I found out it handled some other very large arithmetic better than same java version in use, but i don't have reason for it since I care less about its detail analysis and functionality
 
Upvote 0
Cookies are required to use this site. You must accept them to continue using the site. Learn more…