Need to calculate via Excel:

mod(13^271;162653)

Any thoughts????

Thanks

You need an exponentiator. Look at this website

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

"Diogo" wrote:

Need to calculate via Excel:

mod(13^271;162653)

Any thoughts????

Thanks

no good

but thanks anyway...

Could someone help?

"Joel" wrote:

You need an exponentiator. Look at this website

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

"Diogo" wrote:

Need to calculate via Excel:

mod(13^271;162653)

Any thoughts????

Thanks

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

"Diogo" wrote in message ...
| Need to calculate via Excel:
|
| mod(13^271;162653)
|
| Any thoughts????
|
| Thanks

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




"Diogo" wrote:

no good

but thanks anyway...

Could someone help?

"Joel" wrote:

You need an exponentiator. Look at this website

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

"Diogo" wrote:

Need to calculate via Excel:

mod(13^271;162653)

Any thoughts????

Thanks

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


Diogo wrote:
Need to calculate via Excel:

mod(13^271;162653)

Any thoughts????

Thanks

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


"Equiangular" wrote:

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


Diogo wrote:
Need to calculate via Excel:

mod(13^271;162653)

Any thoughts????

Thanks

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



"Diogo" skrev i meddelelsen
...
Need to calculate via Excel:

mod(13^271;162653)

Any thoughts????

Thanks

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" wrote:

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



"Diogo" skrev i meddelelsen
...
Need to calculate via Excel:

mod(13^271;162653)

Any thoughts????

Thanks

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


"Equiangular" skrev i meddelelsen
...
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


Diogo wrote:
Need to calculate via Excel:

mod(13^271;162653)

Any thoughts????

Thanks

On Jan 16, 10:36 am, "Lazzzx" wrote:
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

"Equiangular" skrev i . gbl...

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

Diogo wrote:
Need to calculate via Excel:

mod(13^271;162653)

Any thoughts????

Thanks

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

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


"Joel" skrev i meddelelsen
...
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" wrote:

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



"Diogo" skrev i meddelelsen
...
Need to calculate via Excel:

mod(13^271;162653)

Any thoughts????

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

"Diogo" wrote:

Need to calculate via Excel:

mod(13^271;162653)

Any thoughts????

Thanks

On Jan 16, 7:30*pm, Jerry W. Lewis wrote:
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.)

Errata....

On Jan 16, 8:11*pm, I wrote:
On Jan 16, 7:30*pm, Jerry W. Lewis wrote:
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.

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!

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


"Diogo" wrote:

Need to calculate via Excel:

mod(13^271;162653)

Any thoughts????

Thanks

Hi Jerry,

Your idea is so great!
Thanks!

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

The correct answer is 102308.

Jerry

"Joel" wrote:

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


"Diogo" wrote:

Need to calculate via Excel:

mod(13^271;162653)

Any thoughts????

Thanks

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

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.

"Jerry W. Lewis" wrote:

The correct answer is 102308.

Jerry

"Joel" wrote:

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


"Diogo" wrote:

Need to calculate via Excel:

mod(13^271;162653)

Any thoughts????

Thanks

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

"Diogo" wrote in message ...
| Need to calculate via Excel:
|
| mod(13^271;162653)
|
| Any thoughts????
|
| Thanks

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

"Niek Otten" wrote:

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

"Diogo" wrote in message ...
| Need to calculate via Excel:
|
| mod(13^271;162653)
|
| Any thoughts????
|
| Thanks

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

"Joel" wrote:

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

"Niek Otten" wrote:

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

"Diogo" wrote in message ...
| Need to calculate via Excel:
|
| mod(13^271;162653)
|
| Any thoughts????
|
| Thanks

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

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


"Jerry W. Lewis" wrote:

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

"Joel" wrote:

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

"Niek Otten" wrote:

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

"Diogo" wrote in message ...
| Need to calculate via Excel:
|
| mod(13^271;162653)
|
| Any thoughts????
|
| Thanks

<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

"Jerry W. Lewis" wrote in message ...
| 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
|

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

--
Dana DeLouis



"Jerry W. Lewis" wrote in message
...
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

"Joel" wrote:

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

"Niek Otten" wrote:

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

"Diogo" wrote in message
...
| Need to calculate via Excel:
|
| mod(13^271;162653)
|
| Any thoughts????
|
| Thanks

I found similar code in this

http://www.xtremevbtalk.com/showthre...=113020&page=3

Dana DeLouis wrote:
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

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


"Niek Otten" wrote in message
...
<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

"Jerry W. Lewis" wrote in message
...
| 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
|

Thanks, Dana!

--
Kind regards,

Niek Otten
Microsoft MVP - Excel

"Dana DeLouis" wrote in message ...
| 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
|
|
| "Niek Otten" wrote in message
| ...
| <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
|
| "Jerry W. Lewis" wrote in message
| ...
| | 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
| |
|
|
|

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


"Niek Otten" wrote:

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

"Diogo" wrote in message ...
| Need to calculate via Excel:
|
| mod(13^271;162653)
|
| Any thoughts????
|
| Thanks

Dana, nice to see you again :)
You had already helped me before in another post. :)