Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
|
Научите умножать натуральные числа 18.05.01 14:37 Число просмотров: 1218
Автор: XR <eXtremal Research> Статус: The Elderman
|
> Где-то когда-то читал (в Ященко кажется), что можно очень
> быстро умножать числа.
> Кажется, там говорили про скорость в ln2 раз медленнее
> сложения.
> И что-то про log говорили, и имя чьё-то (Паскаля что ли).
> Ещё недавно прочитал про такой способ:
> x*y=e^(lnx+lny) но как тогда быстро логарифмировать?
>
> Короче научите. Лень думать над тем, что все знают.
>
> P.S.
> Числа очень большие.
я пользуюсь вот таким вот кодом
// Macros for doing double precision multiply
#define BPU ( 8*sizeof(unsigned) ) // Number of bits in an unsigned
#define lo(x) ( (x) & ((1<<(BPU/2))-1) ) // lower half of unsigned
#define hi(x) ( (x) >> (BPU/2) ) // upper half
#define lh(x) ( (x) << (BPU/2) ) // make upper half
void flex_unit::fast_mul( flex_unit &x, flex_unit &y, unsigned keep )
{
// *this = (x*y) % (2**keep)
unsigned i,limit = (keep+BPU-1)/BPU; // size of result in words
reserve(limit); for (i=0; i<limit; i+=1) a[i] = 0;
unsigned min = x.n; if (min>limit) min = limit;
for (i=0; i<min; i+=1)
{
unsigned m = x.a[i];
unsigned min = i+y.n; if (min>limit) min = limit;
#ifdef topspeed_asm
unsigned c = dmul( m, min-i, y.a, a+i );
unsigned j = min;
#else
unsigned c = 0; // carry
for ( unsigned j=i; j<min; j+=1 )
{
// This is the critical loop
// Machine dependent code could help here
// c:a[j] = a[j] + c + m*y.a[j-i];
unsigned w, v = a[j], p = y.a[j-i];
v += c; c = ( v < c );
w = lo(p)*lo(m); v += w; c += ( v < w );
w = lo(p)*hi(m); c += hi(w); w = lh(w); v += w; c += ( v < w );
w = hi(p)*lo(m); c += hi(w); w = lh(w); v += w; c += ( v < w );
c += hi(p) * hi(m);
a[j] = v;
}
#endif
while ( c && j<limit )
{
a[j] += c;
c = a[j] < c;
j += 1;
}
}
// eliminate unwanted bits
keep %= BPU; if (keep) a[limit-1] &= (1<<keep)-1;
// calculate n
while (limit && a[limit-1]==0) limit-=1;
n = limit;
};
---
Могу прислать весь набор классов (это немного)
|
|
<theory>
|
Научите умножать натуральные числа 17.05.01 20:11
Автор: Бяша <Biasha> Статус: Member
|
Где-то когда-то читал (в Ященко кажется), что можно очень быстро умножать числа.
Кажется, там говорили про скорость в ln2 раз медленнее сложения.
И что-то про log говорили, и имя чьё-то (Паскаля что ли).
Ещё недавно прочитал про такой способ:
x*y=e^(lnx+lny) но как тогда быстро логарифмировать?
Короче научите. Лень думать над тем, что все знают.
P.S.
Числа очень большие.
|
|
Научите умножать натуральные числа 18.05.01 14:37
Автор: XR <eXtremal Research> Статус: The Elderman
|
> Где-то когда-то читал (в Ященко кажется), что можно очень
> быстро умножать числа.
> Кажется, там говорили про скорость в ln2 раз медленнее
> сложения.
> И что-то про log говорили, и имя чьё-то (Паскаля что ли).
> Ещё недавно прочитал про такой способ:
> x*y=e^(lnx+lny) но как тогда быстро логарифмировать?
>
> Короче научите. Лень думать над тем, что все знают.
>
> P.S.
> Числа очень большие.
я пользуюсь вот таким вот кодом
// Macros for doing double precision multiply
#define BPU ( 8*sizeof(unsigned) ) // Number of bits in an unsigned
#define lo(x) ( (x) & ((1<<(BPU/2))-1) ) // lower half of unsigned
#define hi(x) ( (x) >> (BPU/2) ) // upper half
#define lh(x) ( (x) << (BPU/2) ) // make upper half
void flex_unit::fast_mul( flex_unit &x, flex_unit &y, unsigned keep )
{
// *this = (x*y) % (2**keep)
unsigned i,limit = (keep+BPU-1)/BPU; // size of result in words
reserve(limit); for (i=0; i<limit; i+=1) a[i] = 0;
unsigned min = x.n; if (min>limit) min = limit;
for (i=0; i<min; i+=1)
{
unsigned m = x.a[i];
unsigned min = i+y.n; if (min>limit) min = limit;
#ifdef topspeed_asm
unsigned c = dmul( m, min-i, y.a, a+i );
unsigned j = min;
#else
unsigned c = 0; // carry
for ( unsigned j=i; j<min; j+=1 )
{
// This is the critical loop
// Machine dependent code could help here
// c:a[j] = a[j] + c + m*y.a[j-i];
unsigned w, v = a[j], p = y.a[j-i];
v += c; c = ( v < c );
w = lo(p)*lo(m); v += w; c += ( v < w );
w = lo(p)*hi(m); c += hi(w); w = lh(w); v += w; c += ( v < w );
w = hi(p)*lo(m); c += hi(w); w = lh(w); v += w; c += ( v < w );
c += hi(p) * hi(m);
a[j] = v;
}
#endif
while ( c && j<limit )
{
a[j] += c;
c = a[j] < c;
j += 1;
}
}
// eliminate unwanted bits
keep %= BPU; if (keep) a[limit-1] &= (1<<keep)-1;
// calculate n
while (limit && a[limit-1]==0) limit-=1;
n = limit;
};
---
Могу прислать весь набор классов (это немного)
|
| |
Научите умножать натуральные числа 18.05.01 16:27
Автор: Бяша <Biasha> Статус: Member
|
> > Числа очень большие.
В смысле совсем очень большие.
> Могу прислать весь набор классов (это немного)
Пришли - никогда не отказываюсь от исходников:)
Если я правильно понял, здесь перемножались числа ограниченной длины, а мне нужно уметь перемножать натуральные числа (заданные, например, как последовательность слов в системе счисления 2 в степени размер слова).
|
| | |
письмо ушло 18.05.01 17:39
Автор: XR <eXtremal Research> Статус: The Elderman
|
|
|
|
|
подробно о проекте
Анализ криптографических сетевых...
