Search EggHeadCafe's Job Board
EggHeadCafe Silverlight WPF ASP.NET VB.NET C# Excel SQL Server SharePoint
search
Office GroupsView
Excel
Excel Charting
Excel Crashesgpfs
Excel Misc
Excel Newusers
Excel Programming
Excel Setup
Excel Worksheet Functions
Word Application Errors
Word Conversions
Word Customization Menustoolbars
Word Docmanagement
Word Drawing Graphics
Word International Features
Word Mail
Word Mailmerge Fields
Word Newusers
Word Numbering
Word Oleinterop
Word Pagelayout
Word Printingfonts
Word Setup Networking
Word Spelling Grammar
Word Tables
Word Visual Basica Addins
Word Visual Basica Customization
Word Visual Basica General
Word Visual Basica Userforms
Works Win
Office Developer Automation
Office Developer Com Add_Ins
Office Developer Officedev Other
Office Developer Outlook Forms
Office Developer Outlook Visual Basica
Office Developer Visual Basica
Office Misc
Office Setup
Officeupdate
Onenote
Outlook
Outlook Bcm
Outlook Calendaring
Outlook Contacts
Outlook Fax
Outlook General
Outlook Installation
Outlook Interop
Outlook Mac
Outlook Printing
Outlook Program_Addins
Outlook Program_Forms
Outlook Program_Visual Basica
Outlook Teamfolders
Outlook Thirdpartyutil
Project
Project Developer
Project Server
Visio
Visio Developer
Visio General
Word Visual Basica Beginners
Outlookexpress General
Office Communicator
Word Programming
Office Templates Misc

Group SummariesView
.NET Framework
Access
BizTalk
Certifications
CRM
DDK
Exchange Server
FoxPro
French
French .NET
Games
German
German .NET
Graphic Design
IIS
Internet
ISA Server
Italian
Italian .NET
Maps
MCIS
Miscellaneous
Mobile Apps
Money
MSN
Networking
Office
Ops Mgr
Publisher
Security
SharePoint
Small Business
Spanish
Spanish .NET
SQL Server
Systems Management Server
Transaction Server
Virtual PC / Virtual Server
Visual Studio
Win32
Windows 2000
Windows 2003 Server
Windows 7
Windows Live
Windows Media
Windows Update
Windows Vista
Windows XP
 

View All Microsoft Excel Programming Posts  Ask A New Question 

Extreme calculations

Diog posted on Wednesday, January 16, 2008 7:50 AM

Need to calculate via Excel:

mod(13^271;162653)

Any thoughts????

Thanks
reply

 

Extreme calculations

Joe posted on Wednesday, January 16, 2008 7:57 AM

You need an exponentiator.  Look at this website

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

Extreme calculations

Diog posted on Wednesday, January 16, 2008 8:07 AM

no good

but thanks anyway...

Could someone help?
reply

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

Niek Otten posted on Wednesday, January 16, 2008 8: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
reply

You need to build your own math algoritm in strings.

Joe posted on Wednesday, January 16, 2008 8: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
reply

Hi,You may try thisFunction BigMod(base As Long, power As Long, divisor As

Equiangular posted on Wednesday, January 16, 2008 9: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
reply

I got the fist part done by rasing the number to a power of 271.

Joe posted on Wednesday, January 16, 2008 9: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
reply

Hi,Just made this function.

Lazzzx posted on Wednesday, January 16, 2008 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
reply

The problem is with the precision of 13^271.

Joe posted on Wednesday, January 16, 2008 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.
reply

Hi Equingular,(see my posting below)Seems that we got the same mathematical

Lazzzx posted on Wednesday, January 16, 2008 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
reply

Hi Joel,I am not calculating 13^271 at any time.

Lazzzx posted on Wednesday, January 16, 2008 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
reply

Extreme calculations

post_a_repl posted on Wednesday, January 16, 2008 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
reply

Extreme calculations

SteveM posted on Thursday, January 17, 2008 6: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
reply

Extreme calculations

joeu2004 posted on Thursday, January 17, 2008 6: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.)
reply

Extreme calculations

joeu2004 posted on Thursday, January 17, 2008 6: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!
reply

I get the answer 145120 with the following codeSub largemultiply()Dim MyTotal

Joe posted on Thursday, January 17, 2008 7: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
reply

Extreme calculations

Equiangular posted on Thursday, January 17, 2008 8:11 AM

Hi Jerry,

Your idea is so great!
Thanks!
reply

Extreme calculations

post_a_repl posted on Thursday, January 17, 2008 8:19 AM

The correct answer is 102308.

Jerry
reply

Hi Jerry,I implemented the code according to your ideaFunction BigMod2(base As

Equiangular posted on Thursday, January 17, 2008 8: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
reply

I made a slight change and I'm getting 160899 has an answer.

Joe posted on Thursday, January 17, 2008 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.
reply

Very interesting discussions!

Niek Otten posted on Thursday, January 17, 2008 1: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
reply

I still trying to determine the correct answer.

Joe posted on Thursday, January 17, 2008 1: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
reply

Maple and Maxima (both symbolic math programs with unlimited precision) plus

post_a_repl posted on Thursday, January 17, 2008 4: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
reply

VBA mod is limited to numbers that can be coerced to the Long type.

post_a_repl posted on Thursday, January 17, 2008 4: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
reply

I got the right answer. One of my loops was off by one.

Joe posted on Thursday, January 17, 2008 5: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
reply

Niek Otten posted on Thursday, January 17, 2008 5: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
reply

Hi Jerry. Just two cents.

Dana DeLouis posted on Friday, January 18, 2008 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
reply

Extreme calculations

Equiangular posted on Saturday, January 19, 2008 1:24 AM

I found similar code in this

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

 
 

Previous Microsoft Excel Programming conversation.