Overflow using Mod operator 2

[Crundy]

Hello,
I have 3 variables called e, n and m, and I am trying to do this:

dim n, e, z as double
n = 4183
e = 31
m = 5

z = m ^ e
c = z Mod n

But I get an overflow on the mod line. I've tried:

c = fix(z mod n),
c = cDbl(z) mod n

as well as a load of other little things!

Can anyone help?
C:\DOS:>
C:\DOS:>RUN
RUN DOS RUN!!

If this post was useful to you, click the link below

 

[Nannapaneni]

Declare

dim n as double,e as double,z as double

If you declare like
dim n, e, z as double the data types of n,e will be will be variants.

 

[MichaelRed]

Hmmmmm,

MOD is just a shorthand for a recursive divide. Recursion is probably not something you are ready for, so it can (in this case) be expressed as a repetive (LOOP) situation. Although the values selected for the 'sample' may cause some difficulties with rounding and the execution time if 'attacked' in a more or less 'straight forward manner. I think you need to find something which would 'trim' the huge values down to a more manageable domain and then attempt the actual mod. It is not the specific set of values which cause the problem, but more that the overall procedure goal (and possible limits or complications) which give pause to the thought of simply providiing a canned soloution.


Some of your code appears (also) to suffer from lack of explicit declaration ("m" is not decalred), as well as a lack of understanding of the syntax of the dim statement, as you create "n" and "z" as variant and "e" as Double.

Further, the snippet is extracted from some procedure, so it would APPEAR that you want to do SOME operation on a regular basis - but that operation is ill defined and actually appears to only ever return a constant,

MichaelRed
m.red@att.net

There is never time to do it right but there is always time to do it over

 

[LegoArtist]

When using Mod, floating point numbers are converted to integers. If z is too large for a Long then you'll get the overflow error. You might have better luck doing it the "old-fashioned way" (divide the numbers, subtract the integer part and multiply by the denominator) but there, too, you'll eventually run into an overflow error.

 

[strongm]

>MOD is just a shorthand for a recursive divide

Maybe it is on your planet. A more efficient method of implementing a MOD function tends to be repeated subtraction. Which is close to what you seem to be suggesting Crundy write for themself. But why write a longhand version when you've already got the shorthand that does what you want? And even if it is implemented internally in a recursive fashion, so what? As you'll gahter, I don't understand what your reservations concerning MOD are. It sure as heck isn't the cause of the problem Crundy is seeing; Nannapanini has that one nailed.

 

[Crundy]

OK, I've found that I need to use a 'bignum' library to cope with the massive numbers involved (as even a double can't handle them!)

Does anyone know where I can download one from?

P.S. I had previously defined ALL the variables as doubles on individual lines. I just copied and pasted my current attempt into tek-tips C:\DOS:>
C:\DOS:>RUN
RUN DOS RUN!!

If this post was useful to you, click the link below

 

[WilMead]

There was someone else looking for this kind of thing, string multiplication I beleive. Had to do with large primes.

I found this link in thread 222-15520

http://www.freevbcode.com/ShowCode.Asp?ID=1622

BTW: MOD is shorthand for "give me the remainder output from a non floating point division request." Many processors return both the quotient and remainder for non floating point division requests. Since both are made available at the assembly/machine level, programming languages usually include ways to indicate which one to return. Remainders don't exist in floating point arithmetic, so naturally no "shorthand" to fetch them was "invented."


Wil Mead
wmead@optonline.net

 

[Crundy]

I've already seen the SciCalc for large numbers, but there is no documentation with it, and it just appears to be simple mathematical functions.
Am I wrong? If someone thinks otherwise, please let me know how I can use it!!! %-) C:\DOS:>
C:\DOS:>RUN
RUN DOS RUN!!

 

[WilMead]

Take it and add a modulo function expressed in terms of the available functions.

<<<WARNING>>> I HAVE NOT LOOKED AT THE SciCalc for large numbers code!
For example: given sAdd, sSub, sMul, and sDiv to provide whole number arithmatic functions for two very long whole numbers.

sMod(n, e) can be defined as:
t = sDiv(n, e)
t = sMul(n, t)
sMod = sSub(n, t)




Wil Mead
wmead@optonline.net

 

[rvBasic]

The above problem does not necessarily require the use of the specialized &quot;BigNum&quot; program.

Traditional exponentiation is certainly one of the surest ways to obtain an Overflow exception. But the submitted problem is one of Modular exponentation.

Most textbooks on Discrete Arithmetic will show shortcuts to reduce the burden of huge exponentiations and the associated risks of overflow. The following function is based on such an algorithm. It is not free from overflow problems, but it is sufficient for most (student?) non-cryptographic applications.

Private Function ModularExponent(lngBase As Long, lngExponent As Long, lngModulo As Long) As Long

'* Purpose: Calculates the remainder of a modular exponentiation. This is equivalent to
'* ( a ^ b ) MOD m However a brute force exponentiation is prone to Overflow.
'* This procedure reduces the risk of an Overflow (which is NOT entirely eliminated)
'* Accepts: -lngBase: The Base number, a in the above expression
'* -lngExponent: The exponent, b in the above expression
'* -lngModulo: The modulus of the operation, m in the above expression
'* Returns: The residue of the exponentiation
'* NOTE: The algorithm is based on Binary operations and is known as Repeated Squaring

Dim lngHalvedExponent As Long
lngHalvedExponent = Int(lngExponent / 2)

Dim lngHalvedRemainder As Long
lngHalvedRemainder = lngExponent Mod 2

Dim lngDoubledBaseExponent As Long
lngDoubledBaseExponent = 1

Dim lngDoubledBaseRemainder As Long
lngDoubledBaseRemainder = lngBase Mod lngModulo

Dim lngReturnedResidu As Long

Select Case lngDoubledBaseRemainder
Case 0
lngReturnedResidu = 0
GoTo PROC_EXIT
Case Else
Select Case lngHalvedRemainder
Case 0
lngReturnedResidu = 1
Case 1
lngReturnedResidu = lngDoubledBaseRemainder
End Select
End Select

Do While lngDoubledBaseExponent <= lngExponent
lngDoubledBaseExponent = lngDoubledBaseExponent * 2
lngDoubledBaseRemainder = (lngDoubledBaseRemainder * lngDoubledBaseRemainder) Mod lngModulo
lngHalvedRemainder = lngHalvedExponent Mod 2
lngHalvedExponent = Int(lngHalvedExponent / 2)
Select Case lngHalvedRemainder
Case 0
'do nothing
Case 1
lngReturnedResidu = (lngReturnedResidu * lngDoubledBaseRemainder) Mod lngModulo
End Select
Loop

PROC_EXIT:

ModularExponent = lngReturnedResidu

End Function
_________________________________
In theory, there is no difference between theory and practice. In practice, there is. [attributed to Yogi Berra]

 

[MichaelRed]

In the welter of verbage, raskew has the only response which actually provides a useable / testable answer. Furthermore, his soloution is testable within the time I am able to stay on-line and focused on the question.

MichaelRed
m.red@att.net

There is never time to do it right but there is always time to do it over

 

[MarkSweetland]

Who's raskew?

 

[MichaelRed]

Well, I (OBVIOUSLY) blew it AGAIN! It was rvBasic!. Cant read/ cant write / cant code.

MichaelRed
m.red@att.net

There is never time to do it right but there is always time to do it over