Excel - Extreme calculations

Asked By Diog

16-Jan-08 07:50 AM

Need to calculate via Excel:

mod(13^271;162653)

Any thoughts????

Thanks

16-Jan-08 07:57 AM

You need an exponentiator.  Look at this website

http://www.math.temple.edu/~reich/numthy/ModExp.html

16-Jan-08 08:07 AM

no good

but thanks anyway...

Could someone help?

16-Jan-08 08:28 AM

You need to build your own math algoritm in strings.  It is not really that
hard, just requires a little bit of time (about 2-3 hours).

The code for multiplying would look something like the code below.  You'll
need to call the multiplying routine 271 times.  Then write a similar divvide
functtion.

Function multiply(parm1 as string, parm2 as string)

Total = ""
carry = 0
for i = 1 to len(parm1)
mychar1 = right(parm1,i)
for j = 1 to len(parm2)
mychar2 = right(parm2,i)

prod = (val(mychar1) * val(mychar2)) + carrruy
carry = int(prod/10)
remainder = prod mod 10
total = format(remainder,"text") & total
next j

16-Jan-08 08:27 AM

Excel's precision limits (15 decimal digits) seem to cause problems.

You could try a multi-precision add-in. if you still consider that Excel.

Here's one, there may be more

http://precisioncalc.com:80/

--
Kind regards,

Niek Otten
Microsoft MVP - Excel

16-Jan-08 09:17 AM

Hi,

You may try this

Function BigMod(base As Long, power As Long, divisor As Long) As Long

Dim i As Long

BigMod = 1
For i = 1 To power
BigMod = (BigMod * (base Mod divisor)) Mod divisor
If BigMod = 0 Then Exit For
Next i

End Function

16-Jan-08 09:55 AM

I got the fist part done by rasing the number to a power of 271.  the answer
is a string.  Now you need to do the same idea for division.


Sub largemultiply()
Dim MyTotal As String

MyTotal = "13"
For i = 1 To 270
MyTotal = Multiply(MyTotal, "13")
Next i


End Sub

Function Multiply(parm1 As String, parm2 As String) As String

Multiply = ""
carry = 0
For i = 0 To (Len(parm1) - 1)
mychar1 = Mid(parm1, Len(parm1) - i, 1)
total = ""
For j = 0 To (Len(parm2) - 1)
mychar2 = Mid(parm2, Len(parm2) - j, 1)

prod = (Val(mychar1) * Val(mychar2)) + carry
carry = Int(prod / 10)
remainder = prod Mod 10
total = Trim(CStr(remainder)) & total
Next j
If Multiply = "" Then
Multiply = total
Else
Multiply = Add(Multiply, total, i)
End If
Next i

End Function
Function Add(Multiply, total, shift)

carry = 0
If shift > 0 Then
Add = Right(Multiply, shift)
Else
Add = ""
End If
For i = 0 To Len(total) - 1
If Len(Multiply) > (i + shift) Then
add1 = Val(Mid(Multiply, Len(Multiply) - (i + shift), 1))
Else
add1 = 0
End If
add2 = Val(Mid(total, Len(total) - i, 1))
Sum = add1 + add2 + carry
carry = Int(Sum / 10)
bit = Sum Mod 10
Add = bit & Add
Next i
If carry <> 0 Then
Add = carry & Add
End If
End Function

16-Jan-08 10:20 AM

Hi,
Just made this function. You can use it if you are only interested in x^n
(mod M) and not x^n. The formula is a so-called recursive that calls itself
N times. The trick is to calculate the Modulus before calculating the next
step. I have no mathematical proof that is is correct (I'm not
mathematician), but I tested it on different calculations and saw no
difference from "=MOD(X^N;M)". Like feed-back if anyone thinks that the
function has any flaws.

rgds,
Lazzzx

Function ExpMod(X As Long, N As Long, M As Long) As Long
Static R As Long
If R = 0 Then R = 1
If N > 0 Then R = (R Mod M) * X * ExpMod(X, N - 1, M)
ExpMod = R Mod M
R = 1
End Function

16-Jan-08 10:33 AM

The problem is with the precision of 13^271.  Using a LONG variable is not
going to get you the precision of getting an exact modulus number.  You are
only going to get about 16 decimal place accuracy.

16-Jan-08 10:36 AM

Hi Equingular,
(see my posting below)
Seems that we got the same mathematical idea... solved i a little differntly
in programming. Just tested your function versus my function on different
scenarios. Came out with the same result. Even for the calculation posted by
OP, ie.  mod(13^271;162653)=102.308.

regards,
Lazzzx

16-Jan-08 11:08 AM

Hi Joel,
I am not calculating 13^271 at any time. Before multiplying with X I
calculate X (mod M). Since X (mod M)< M, i will never make a calculation of
R bigger than M * X. I the case given by OP R * X is 13 * 162.165 =
2.114.489. R will always be smaller than this number, hence no problem with
precission.

rgds,
Lazzzx

17-Jan-08 06:38 AM

Of course you could just subtract the logs of both sides and then take
the anti-log of the fractional part of the result.  i.e.

271 log 13 - log 162653

but maybe that is too easy.

SteveM

16-Jan-08 10:30 PM

Two additional approaches that you could consider:

The simplest approach is to download Maxima from
http://maxima.sourceforge.net/index.shtml
and use it to directly calculate mod(13^271,162653);

Or you could note that =Mod(13^5,162653) returns 45987,
so that 152516  =Mod(45987^2) is equivalent to =Mod(13^10,162653)
hence 124726  =Mod(152516^2) is equivalent to =Mod(13^20,162653)
...
this accelerates the process used by Equiangular's algorithm.

Jerry

17-Jan-08 06:39 AM

I believe that 13^14 is the largest power of 13 that can be
represented accurately in a 64-bit floating-point number.  So I would
not go any higher than that.  In fact, in Excel, =3DMOD(13^20,162653)
returns a #NUM error.



Since Equiangular's algorithm was written in VBA, perhaps you are
thinking of the 64-bit mantissa of the FPU.  But the VBA mod operator
seems to limit operands to a 32-bit signed integer.  So I believe that
13^8 is the largest power of 13 that can be used.  (VBA gives an error
for anything larger than 2^31-1.)

17-Jan-08 06:39 AM

Errata....


Sorry.  I misread your posting.  You are not suggesting the use of
13^20.  Instead, you are suggesting a smaller number that is
equivalent to it.  Mea culpa!

17-Jan-08 07:41 AM

I get the answer 145120 with the following code

Sub largemultiply()
Dim MyTotal As String

MyTotal = "13"
For i = 1 To 270
MyTotal = Multiply(MyTotal, "13")
Next i

Remainder = Divide(MyTotal, "162653")
End Sub

Function Multiply(parm1 As String, parm2 As String) As String

Multiply = ""
carry = 0
For i = 0 To (Len(parm1) - 1)
mychar1 = Mid(parm1, Len(parm1) - i, 1)
total = ""
For j = 0 To (Len(parm2) - 1)
mychar2 = Mid(parm2, Len(parm2) - j, 1)

prod = (Val(mychar1) * Val(mychar2)) + carry
carry = Int(prod / 10)
Remainder = prod Mod 10
total = Trim(CStr(Remainder)) & total
Next j
If Multiply = "" Then
Multiply = total
Else
Multiply = Add(Multiply, total, i)
End If
Next i

End Function
Function Add(Multiply, total, shift)

carry = 0
If shift > 0 Then
Add = Right(Multiply, shift)
Else
Add = ""
End If
For i = 0 To Len(total) - 1
If Len(Multiply) > (i + shift) Then
add1 = Val(Mid(Multiply, Len(Multiply) - (i + shift), 1))
Else
add1 = 0
End If
add2 = Val(Mid(total, Len(total) - i, 1))
Sum = add1 + add2 + carry
carry = Int(Sum / 10)
bit = Sum Mod 10
Add = bit & Add
Next i
If carry <> 0 Then
Add = carry & Add
End If
End Function

Function Divide(Quotent, Divisor)
Dim Remainder As Long

NDivisor = Val(Divisor)
NewQuotent = Val(Left(Quotent, Len(Divisor)))
loops = (Len(Quotent) - Len(Divisor))
For i = 0 To loops
Remainder = NewQuotent Mod NDivisor
If i <> loops Then
Newbit = Mid(Quotent, i + Len(Divisor) + 1, 1)
NewQuotent = (Remainder * 10) + Val(Newbit)
End If
Next i
Divide = Remainder
End Function

17-Jan-08 08:11 AM

Hi Jerry,

Your idea is so great!
Thanks!

17-Jan-08 08:19 AM

The correct answer is 102308.

Jerry

17-Jan-08 08:47 AM

Hi Jerry,

I implemented the code according to your idea

Function BigMod2(base As Long, power As Long, divisor As Long) As Long

Dim temp As Long

If power = 1 Then
BigMod2 = base Mod divisor
ElseIf power Mod 2 = 0 Then ' even power
temp = BigMod2(base, power \ 2, divisor)
BigMod2 = temp * temp Mod divisor
Else ' odd power
temp = BigMod2(base, power \ 2, divisor)
BigMod2 = (((temp * temp) Mod divisor) * base) Mod divisor
End If

End Function

However, I got #VALUE! error for 13^271 mod 162653
It fails when calculating 13^33 mod 162653

as 13^16 mod 162653 = 75280
so 75280 * 75280 mod 162653 = 5667078400 mod 162653
but 5667078400 > 2^31-1

Actually my original solution also encounters such error for cases like
65535^2 mod 65536

17-Jan-08 10:46 AM

I made a slight change and I'm getting 160899 has an answer.  I had one loop
counter going once too many.  Are you sure your answer is correct?  I don't
see what is wrong with my method of using string to get the answer.

17-Jan-08 01:22 PM

Very interesting discussions!
But I have hardly seen Diogo (the OP) again.
My question: What would one need such a calculation for?

--
Kind regards,

Niek Otten
Microsoft MVP - Excel

17-Jan-08 01:31 PM

I still trying to determine the correct answer.  I fixed some problems with
my code and getting the answer 59026.  Did anybody else get the answer that
Jerry got 102308

Sub largemultiply()
Dim MyTotal As String

MyTotal = "13"
For i = 1 To 270
MyTotal = Multiply(MyTotal, "13")
Next i

Remainder = Divide(MyTotal, "162653#")
End Sub

Function Multiply(parm1 As String, parm2 As String) As String

Multiply = ""

For i = 0 To (Len(parm2) - 1)
carry# = 0
mychar2 = Mid(parm2, Len(parm2) - i, 1)
total = ""
For j = 0 To (Len(parm1) - 1)
mychar1 = Mid(parm1, Len(parm1) - j, 1)

prod = (Val(mychar1) * Val(mychar2)) + carry
carry = Int(prod / 10)
Remainder# = prod Mod 10
total = Trim(CStr(Remainder)) & total
Next j
If Multiply = "" Then
If carry = 0 Then
Multiply = total
Else
Multiply = Trim(CStr(carry)) & total
End If
Else
Multiply = Add(Multiply, total, i)
End If
Next i

End Function
Function Add(Multiply, total, shift)

carry = 0
If shift > 0 Then
Add = Right(Multiply, shift)
Else
Add = ""
End If
loops = Len(total)
If (Len(Multiply) - shift) > loops Then
loops = Len(Multiply) - shift
End If
For i = 0 To loops - 1
If Len(Multiply) - shift > i Then
add1 = Val(Mid(Multiply, Len(Multiply) - (i + shift), 1))
Else
add1 = 0
End If
add2 = Val(Mid(total, Len(total) - i, 1))
Sum# = add1 + add2 + carry
carry = Int(Sum / 10)
bit = Sum Mod 10
Add = bit & Add
Next i
If carry <> 0 Then
Add = carry & Add
End If
End Function

Function Divide(Quotent, Divisor)
Dim Remainder As Long

NDivisor = Val(Divisor)
NewQuotent = Val(Left(Quotent, Len(Divisor)))
loops = (Len(Quotent) - Len(Divisor))
For i = 0 To (loops - 1)
Remainder = NewQuotent Mod NDivisor
If i <> loops Then
Newbit = Mid(Quotent, i + Len(Divisor) + 1, 1)
NewQuotent = (Remainder * 10) + Val(Newbit)
End If
Next i
Divide = Remainder
End Function

17-Jan-08 04:37 PM

Maple and Maxima (both symbolic math programs with unlimited precision) plus
Equiangular's VBA code all agree that mod(13^271,162653) is 102308.

Jerry

17-Jan-08 04:49 PM

VBA mod is limited to numbers that can be coerced to the Long type.  Thus
anything greater than 2.147483647E+09 will overflow.  In particular, your
original function would fail for general problems mod 162653, since
162652*162652 = 2.65E+10.

The worksheet MOD function works with double precision integers, but has
some surprising limitations that have been documented in earlier threads.
You can either "roll your own" mod function (the most robust approach) or use
the VBA Evaluate() function to access the worksheet MOD function.

Jerry

17-Jan-08 05:11 PM

I got the right answer.  One of my loops was off by one.  Here is actual
macro code that works!!!!!   My code is also a partical symbolic amath
program.  the multiple is completely symbolic.  The divide function I cheated
because the data only need 162653 modulus which was small enough to use the
excel math functions.


Sub largemultiply()
Dim MyTotal As String

MyTotal = "13"
For i = 1 To 270
MyTotal = Multiply(MyTotal, "13")
Next i

Remainder = Divide(MyTotal, "162653")
End Sub

Function Multiply(parm1 As String, parm2 As String) As String

Multiply = ""

For i = 0 To (Len(parm2) - 1)
carry# = 0
mychar2 = Mid(parm2, Len(parm2) - i, 1)
total = ""
For j = 0 To (Len(parm1) - 1)
mychar1 = Mid(parm1, Len(parm1) - j, 1)

prod = (Val(mychar1) * Val(mychar2)) + carry
carry = Int(prod / 10)
Remainder# = prod Mod 10
total = Trim(CStr(Remainder)) & total
Next j
If Multiply = "" Then
If carry = 0 Then
Multiply = total
Else
Multiply = Trim(CStr(carry)) & total
End If
Else
Multiply = Add(Multiply, total, i)
End If
Next i

End Function
Function Add(Multiply, total, shift)

carry = 0
If shift > 0 Then
Add = Right(Multiply, shift)
Else
Add = ""
End If
loops = Len(total)
If (Len(Multiply) - shift) > loops Then
loops = Len(Multiply) - shift
End If
For i = 0 To loops - 1
If Len(Multiply) - shift > i Then
add1 = Val(Mid(Multiply, Len(Multiply) - (i + shift), 1))
Else
add1 = 0
End If
add2 = Val(Mid(total, Len(total) - i, 1))
Sum# = add1 + add2 + carry
carry = Int(Sum / 10)
bit = Sum Mod 10
Add = bit & Add
Next i
If carry <> 0 Then
Add = carry & Add
End If
End Function

Function Divide(Quotent, Divisor)
Dim Remainder As Double
Dim NewQuotent As Double
Dim NDivisor As Double

NDivisor = Val(Divisor)
NewQuotent = Val(Left(Quotent, Len(Divisor)))
loops = (Len(Quotent) - Len(Divisor))
For i = 0 To loops
Remainder = NewQuotent Mod NDivisor
Newbit = Mid(Quotent, i + Len(Divisor) + 1, 1)
NewQuotent = (Remainder * 10) + Val(Newbit)
Next i
Divide = Remainder

End Function

17-Jan-08 05:12 PM

threads>

I thought I remembered that, but I couldn't find it using Google's Group search.
Do you have some sort of key to that thread? I'd like to keep it for future reference

--
Kind regards,

Niek Otten
Microsoft MVP - Excel

18-Jan-08 12:42 PM

Hi Jerry.  Just two cents.  (I'm missing some of the threads here)
In math programs, mod(13^271,162653) is usually done more efficiently via a
number theory algorithm that usually goes by the name "PowerMod."

Hence:
PowerMod[13, 271, 162653]

102308

For the op, the vba algorithm usually follows Equiangular's code, where the
'p term is represented in base two.  This allows vba to work with very large
numbers. (above 15 if you wish, although the code is a little tricky)

In Vba:

n=123456789012346

?PowerMod(n,n+1,n+2)
30910517478724

--
Dana DeLouis

19-Jan-08 01:24 AM

I found similar code in this

http://www.xtremevbtalk.com/showthread.php?t=113020&page=3