Extreme calculations

[Diogo]

Need to calculate via Excel:

mod(13^271;162653)

Any thoughts????

Thanks

 

[Joel]

You need an exponentiator. Look at this website

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

 

[Diogo]

no good

but thanks anyway...

Could someone help?

 

[Niek Otten]

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

| Need to calculate via Excel:
|
| mod(13^271;162653)
|
| Any thoughts????
|
| Thanks

 

[Joel]

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

 

[Equiangular]

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

 

[Joel]

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

 

[Lazzzx]

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

 

[Joel]

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.

 

[Lazzzx]

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

 

[SteveM]

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

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's too easy.

SteveM

 

[Lazzzx]

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

 

[Jerry W. Lewis]

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

 

[joeu2004]

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)

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, =MOD(13^20,162653)
returns a #NUM error.

this accelerates the process used by Equiangular's algorithm.

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.)

 

[joeu2004]

Errata....

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.

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!

 

[Joel]

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

 

[Equiangular]

Hi Jerry,

Your idea is so great!
Thanks!

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

 

[Jerry W. Lewis]

The correct answer is 102308.

Jerry

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

 

[Equiangular]

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

 

[Joel]

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.