Цитата(V.A.KeRneL @ 27.1.2007, 09:14  ) | | так что можно обойтись, используя только логарифмическое число умножений.» |
V.A.KeRneL, добавлю немного кода с пояснением мелочей 
bas^pot=power(bas,pot)
| Код |
int power (int bas, int pot) {
//В надежде на то, что компилер соптимирует pot%2 на pot&1 и pot /= 2 на pot>>1.
int p = 1;
while (pot > 0) {
if (pot%2) { p = p * bas ; }
bas = bas * bas ;
pot / =2;
}
return p;
}
|
Если pot постоянный для нескольких чисел, то можно один раз просто разбить его на биты и вместо pot%2 проверять, имеет бит значение 1, или 0.
| Код |
int main()
{
int bas[]{123,34,546,678};
int pot=98;
int bitmasklength;
int *potmask=toBitmask(pot,&bitmasklength);
for(int i=0;i<sizeof(bas);i++)
{
printf("%i^%i=%i\n",bas[i],pot,power (bas, potmask,bitmasklength));
}
delete potmask;
}
int power (int bas, int *potmask,int potmasklength) {
int p = 1;
for (int i=0;i<potmasklength;i++) {
if (pot[i]) { p = p * bas ; }
bas = bas * bas ;
}
return p;
}
int*potmask(int pot, int*length)
{
int *newmask=new int[32]; //максималъно 32 бита у нас тут
int i=0;
while (pot > 0) {
newmask[i]=pot%2
pot / =2;i++;
}
*length=i;
return newmask;
}
|
Если необходимо работать по модулю какого-то числа (n), то в цикле надо просто это (%n) вписать после каждого умножения
PS: Код к сожалению проверить не было возможности. Написан "на коленке"
PPS: Вобще-то эти способы (для умножения, степени, проверки на простоту) разработал http://ru.wikipedia.org/wiki/%D0%9B%D0%B0%D0%B3%D1%80%D0%B0%D0%BD%D0%B6%2C_%D0%96%D0%BE%D0%B7%D0%B5%D1%84_%D0%9B%D1%83%D0%B8
Хотя быстрое умножение было известно ещё в древнем Египте.
|