15,918,808 members
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 5:19am
v3
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.

Solution 1

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.

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
nv3 27-Jun-13 14:57pm
Thank you!

Solution 2

On the tails of Solution 1, you have a couple of things that you might do to improve the speed a bit...

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;
}```

v3