Click here to Skip to main content
15,844,752 members
Please Sign up or sign in to vote.
2.00/5 (1 vote)
See more:
I am trying to perform the following operation :

intgr[i]= getmod(power(*(str+i),a),b);


The above code is an expression inside a 'for - loop'.

where 1. getmod(x,y) = x mod y.
2. power(x,y) = x y.

Here i use the exponentiation by squaring algorithm for calculating power().

3. '*' is the pointer operation.
4. Variable 'i' is a counter of a 'for - loop'.

But still the calculation is slower. The calculation is done as part of implementing the RSA algorithm.

Is there any good method for speeding up the operation highlighted.
Posted
Updated 27-Jun-13 6:19am
v3
Comments
Sergey Alexandrovich Kryukov 27-Jun-13 11:28am    
Where is the signature of the method power and its implementation? If this is numeric and taken from some well-know library, you hardly can improve it.
If this is your own code, it could be bad; one example of prohibitively bad solution is multiplication of y operands.
—SA
lewax00 27-Jun-13 19:00pm    
Any reason you aren't using the % operator instead of a function? Should be faster than function call.

I assume you are dealing here with big (multi-word) integers, as the context is encryption. If that is so you can make use of the fact that
C++
mod (a**b) = mod (mod(a) ** b)

And that might be significantly faster if you use the multiplying approach for computing the power. Note that mod(a) is usually significantly smaller than a, and hence computing mod(a)**b is usually faster than computing a ** b.

I am no big-int expert, but I would also consider using a faster algorithm for the power computation than the squaring approach.
 
Share this answer
 
Comments
compuknow 27-Jun-13 12:48pm    
Actually , what do mean by the symbol '**'. Is it product (Multiplication) ?
nv3 27-Jun-13 14:56pm    
** means exponentiation, i.e. your power (a, b) function.
JackDingler 27-Jun-13 14:58pm    
It's shorthand for the power function.
zlogdan 27-Jun-13 13:01pm    
5 stars answer.
nv3 27-Jun-13 14:57pm    
Thank you!
On the tails of Solution 1, you have a couple of things that you might do to improve the speed a bit...

Don't add to the pointer but increment it instead.
C++
intgr[i]= getmod(power(*(str++),a),b);


The std library pow method uses floats. This means that the function has to be concerned with fractional powers. With integers, you don't need that overhead.

If you know that you're only going to use integers, then write your own version and make it inline or a template.

The compiler may be able to further optimize the code when it is inline.

You may look at similar optimizations for mod()

Example / Note that you can't use negative values for the exponent.
C++
#include "stdafx.h"
#include <conio.h>
#include <math.h>

template <class T0, class T1, class T2>
T0 _power(T1 v, T2 exp)
{
    T0 result = 1;

    while (exp--)
        result *= v;

    return result;
}

int _tmain(int argc, _TCHAR* argv[])
{
    unsigned int a = 2;
    unsigned int b = 3;

    unsigned __int64 c = _power<unsigned __int64, unsigned int, unsigned int>(a, b);

    printf("%I64u", c);

    _getch();

	return 0;
}
 
Share this answer
 
v3

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900