Thread: overflow problem

  1. #1
    Registered User
    Join Date
    Mar 2002
    Posts
    2

    overflow problem

    Hi there,
    I have included code for a function called powermod which performs the following equation a^b mod(N), in which a, b and N are all defined as longs. However when I use large values for b, the function overflows and returns a wrong value. Does anyone know if there is a way around this?

    // powermod function
    // -----------------
    // this function raises a number (value) to a power, under a given
    // modulus.

    long powermod(long value, long power, long modulus)
    {
    int temp;
    long ret(1);
    long t_value;

    for(unsigned int i = 0;i < (sizeof(power)*8);++i)
    {
    if (i == 0)
    {
    t_value = value;
    }

    else
    {
    t_value *= t_value;
    t_value %= modulus;
    }

    temp =((power >> i) & 1);
    if ( temp == 1)
    {
    // the ith bit is 1, so we are going to
    // need to include this t value in our
    // answer.

    ret *= t_value;
    ret %= modulus;
    }
    }

    return ret;
    }

  2. #2
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    you can try using long doubles as the type instead of long. the long double type is the largest built in type. If you need something bigger than that, then you will have to create the type yourself. Unfortunately, the modulus operator is only defined for type int. You might be able to overload it for other types, but I've never done so.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Stack overflow errors in 3 areas
    By ulillillia in forum C Programming
    Replies: 13
    Last Post: 04-29-2007, 03:20 PM
  2. WS_POPUP, continuation of old problem
    By blurrymadness in forum Windows Programming
    Replies: 1
    Last Post: 04-20-2007, 06:54 PM
  3. Laptop Problem
    By Boomba in forum Tech Board
    Replies: 1
    Last Post: 03-07-2006, 06:24 PM
  4. half ADT (nested struct) problem...
    By CyC|OpS in forum C Programming
    Replies: 1
    Last Post: 10-26-2002, 08:37 AM
  5. binary tree problem - help needed
    By sanju in forum C Programming
    Replies: 4
    Last Post: 10-16-2002, 05:18 AM