Двадцять третя лекція другого сезону відбудеться 5 травня о 18 годині у конференц-залі на третьому поверсі.
Лекцію ведуть: Олександр та Мар’ян.
Тема: Довга арифметика.
На порядку денному:
- Основні ідеї;
- Елементарні операції з короткими числами;
- Множення та ділення на довге число;
- Вибір основи числення та вивід довгого числа;
- Готові реалізації довгої арифметики.
Якщо комусь цікаво, то я потестив рішення “N^3″, що було запропоноване на лекції для множення довгого на довге. Як я і передбачав, там зовсім не N^3, а N^2 навіть для найгіршого випадку (думаю, що ним є 999…999 * 999…999). Отже, множення двох таких чисел довжинами N в системі числення 1000 000 000 займало:
N=1000: 0.087 c
N=2000: 0.36 c
N=5000: 2.2 c
N=10000: 8.8 c
N=20000: 35.6 c
Максимальна кількість ітерацій внутрішнього циклу при i=1, j=0 складає N, але середня кількість ітерацій для всього множення – 1.999 – ніби прямує до 2 =).
Отже, маємо чистий N^2 і без всяких проблем з відкладанням і накопиченням оверфловів.
PS: Якщо хтось не в курсі (а таких ніби більшість), то мова йде про наступну реалізацію:
#include
#include
const int L = 50000;
const int mod = 1000000000;
struct LVal
{
int v[L];
int l;
};
LVal a,b;
int max(int a, int b)
{
return a>b?a:b;
}
LVal LMul(LVal &a, LVal &b)
{
LVal c;
long long x;
int y;
int z;
int i,j,k;
int carr;
int cs = 0;
for(i=0; i<L; i++)
{
c.v[i]=0;
}
clock_t begin=clock();
int maxcarry = 0;
for (i=0; i<a.l; i++)
{
for (j=0; j0; k++, carr++)
for(k=i+j+1; z>0; k++)
{
y = c.v[k]+z;
c.v[k]=y%mod;
z = y/mod;
}
//cs+=carr;
//maxcarry = max(maxcarry, carr);
}
}
clock_t end=clock();
//printf(”MaxCarry: %d\n”, maxcarry);
//printf(”AvgCarry: %lf\n”, cs/(double)(a.l*b.l));
printf(”Mult time: %lf ms\n”, (double)(end-begin)/CLOCKS_PER_SEC);
c.l = a.l+b.l-1 + (c.v[a.l+b.l-1]>0 ? 1 : 0);
return c;
}
void LPrint(LVal a)
{
printf(”%d”, a.v[a.l-1]);
for (int i=a.l-2; i>=0; i–)
{
printf(”%09d”, a.v[i]);
}
}
int main()
{
int testLen = 20000;
for (int i=0; i<testLen; i++)
{
a.v[i]=999999999;
b.v[i]=999999999;
}
a.l=testLen;
b.l=testLen;
printf("%d", LMul(a, b).l);
return 0;
}
В коді вище мабуть єж якась послідовність символів, що замість коменту зробила його жирним =). Тому перший жирний рядок, що не буде компілитись, варто закоментувати =)).
Напиши, що мало бути на місці цього рядка і я поправлю
for (j=0; j0; k++, carr++)
Ось основний цикл, надіюсь, тепер буде без ескейпів (раніше “менше b” вважалось початком HTML-тегу) =)
for (i=0; i < a.l; i++)
{
for (j=0; j 0; k++)
{
y = c.v[k]+z;
c.v[k]=y%mod;
z = y/mod;
}
}
}
Ще одна невлада спроба =). Дубль 3, тепер вже точно все поескейпив =))) :
for (i=0; i<a.l; i++)
{
for (j=0; j<b.l; j++)
{
x = a.v[i]*(long long)b.v[j] + c.v[i+j];
c.v[i+j]=x%mod;
z = x/mod;
for(k=i+j+1; z>0; k++)
{
y = c.v[k]+z;
c.v[k]=y%mod;
z = y/mod;
}
}
}