информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Все любят медАтака на InternetГде водятся OGRы
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Очередное исследование 19 миллиардов... 
 Оптимизация ввода-вывода как инструмент... 
 Зловреды выбирают Lisp и Delphi 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / theory
Имя Пароль
если вы видите этот текст, отключите в настройках форума использование JavaScript
ФОРУМ
все доски
FAQ
IRC
новые сообщения
site updates
guestbook
beginners
sysadmin
programming
operating systems
theory
web building
software
hardware
networking
law
hacking
gadgets
job
dnet
humor
miscellaneous
scrap
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
Научите умножать натуральные числа 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
<"чистая" ссылка>
1




Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2025 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach