Extreme calculations

N

Niek Otten

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

--
Kind regards,

Niek Otten
Microsoft MVP - Excel

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

Joel

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
 
J

Jerry W. Lewis

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
 
J

Jerry W. Lewis

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
 
J

Joel

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
 
N

Niek Otten

<MOD function works with double precision integers, but has some surprising limitations that have been documented in earlier
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

| 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
|
| "Equiangular" wrote:
|
| > 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
| >
| > Jerry W. Lewis wrote:
| > > 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
| > >
| > > "Diogo" wrote:
| > >
| > >> Need to calculate via Excel:
| > >>
| > >> mod(13^271;162653)
| > >>
| > >> Any thoughts????
| > >>
| > >> Thanks
| >
 
D

Dana DeLouis

and use it to directly calculate mod(13^271,162653);

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
 
E

Equiangular

I found similar code in this

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

Dana said:
and use it to directly calculate mod(13^271,162653);
Click to expand...

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
Click to expand...
 
D

Dana DeLouis

Do you have some sort of key to that thread? I'd like to keep it for
future reference
Click to expand...

Is this what you are looking for?

XL: MOD() Function Returns #NUM! Error Value
http://support.microsoft.com/kb/119083/en-us

The reason math programs use PowerMod is that a call like this:

Mod(81703396 ^ 81703396, 23)

would require an intermediate calculation of an exact integer with over
646,000,000 digits in it.
However, it's a very fast calculation via code.

?PowerMod(81703396, 81703396, 23)

4
 
N

Niek Otten

Thanks, Dana!

--
Kind regards,

Niek Otten
Microsoft MVP - Excel

|> Do you have some sort of key to that thread? I'd like to keep it for
| > future reference
|
| Is this what you are looking for?
|
| XL: MOD() Function Returns #NUM! Error Value
| http://support.microsoft.com/kb/119083/en-us
|
| The reason math programs use PowerMod is that a call like this:
|
| Mod(81703396 ^ 81703396, 23)
|
| would require an intermediate calculation of an exact integer with over
| 646,000,000 digits in it.
| However, it's a very fast calculation via code.
|
| ?PowerMod(81703396, 81703396, 23)
|
| 4
|
| --
| Dana DeLouis
|
|
| | > <MOD function works with double precision integers, but has some
| > surprising limitations that have been documented in earlier
| > 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
| >
| > | > | 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
| > |
| > | "Equiangular" wrote:
| > |
| > | > 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
| > | >
| > | > Jerry W. Lewis wrote:
| > | > > 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
| > | > >
| > | > > "Diogo" wrote:
| > | > >
| > | > >> Need to calculate via Excel:
| > | > >>
| > | > >> mod(13^271;162653)
| > | > >>
| > | > >> Any thoughts????
| > | > >>
| > | > >> Thanks
| > | >
| >
| >
|
 
D

Diogo

Hello everyone.

I've been away for a while and return to see that this thread has grown;
very interesting discussions going around in my absence... :) need to catch
up :)

Answering Niek Otten question this post begun because I was trying to
calculate Mod97 function to implement a check digit for optical lines in bank
cheques, and the evolved to trying RSA algorithm in an Excel sheet... :)
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

conditional format fails when copied 1
Time Now() minus ten minutes 1
Help with Calculating Using Macro Pleaseeeeeeee 1
Calculating Time 2
Return fractional part of values 3
circular referencing of formulae when setting calculation back toautomatic from manual 2
Overriding the calculation state 6
Launching the Windows Calculator via vb, how? (Not the toolbar customize one, just actual vb code?) 12

Top