Форум на Исходниках.RU https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=50485&view=findpost&p=394258 Fri, 02 Jul 2004 19:05:48 +0000 Математика https://forum.sources.ru/index.php?showtopic=50485&view=findpost&p=394258 Как быстро делить/умножать числа на степень двойки?

Как известно, опрерации умножения и деления занимаю много машинного времени. Если требуется скорость, то целесообразно использовать логические сдвиги:

     
    i:=i shl 1; { i:=i * 2^1}
    i:=i shl 2; { i:=i * 2^2}
    {и т.д.}
    i:=i shr 1; { i:=i div 2^1}
    i:=i shr 2; { i:=i div 2^2}
    {и т.д.}


Примечание: корректно работает только с целыми беззнаковыми типами (word, byte...)!
Если производить эти операции со знаковыми типами, то бит знака тоже сдвигается и в рез-те
число может поменять свой знак!

Сообщения были разделены в тему "Численные методы"]]> e-moe Pascal: Математика https://forum.sources.ru/index.php?showtopic=50485&view=findpost&p=378476 Fri, 11 Jun 2004 09:37:07 +0000 Математика https://forum.sources.ru/index.php?showtopic=50485&view=findpost&p=378476 Как узнать из каких цифр состоит целое число?
    Var X : Integer;
    Begin
     X:=12345;
     Writeln('Число состоит из таких цифр:');
     While X <> 0 Do
      Begin
       Writeln(X Mod 10);
       X:=X Div 10;
      End;
    End.
]]> romtek Pascal: Математика https://forum.sources.ru/index.php?showtopic=50485&view=findpost&p=332504 Tue, 06 Apr 2004 08:15:16 +0000 Математика https://forum.sources.ru/index.php?showtopic=50485&view=findpost&p=332504 Более быстрое разложение числа на множители.
В методе, описанном romtek-ом, количество проверок пропорционально sqrt(N), т.е. для разложение числа порядка 1012 потребуется около 106 операций, причем используется деление!
Существуют методы поиска делителей, которые справляются со своей задачей намного быстрее (без операций деления).
В методе Ферма предполагается, что N - нечетное число, причем N = uv. Попробуем подобрать такие числа X и Y, что будет выполняться:
N = p2 - q2. Обозначим u = (p + q) / 2 и v = (p - q) / 2.
Будем пытаться приблизить числа p и q с разных сторон, чтобы выполнялось N = p2 - q2.
Итак, сам алгоритм:
* Присвоим x = 2 * trunc(sqrt(N)) + 1, y = 1, r = sqr(trunc(sqrt(N))) - N (во время выполнения алгоритма числа x, y и r будут соответствовать 2p + 1, 2q + 1 и p2 - q2 - N)
* Если r = 0, то выполнение алгоритма заканчивается. Имеем N = ((x-y)/2)((x+y-2)/2) и (x-y)/2 - наибольши делитель числа N.
* Присвоить r = r + x, x = x + 2 (шаг по x)
* Присовить r = r - y, y = y - 2 (шаг по y). Делать этот шаг, пока r > 0.
* Перейти к проверке r = 0

Так как все действия алгоритма - это сложения и вычитания, то они на компьютере выполняются очень быстро. В результате работы алгоритма будет получено одно число - наибольший делитель числа N. Замечание: данный алгоритм лучше использовать для поиска больших делителей, нежели для маленьких!
    {$N+,E+}
    Function FermaFactorization(N : Comp) : Comp;
    Var X, Y, R : Comp;
    Begin
     X:=2 * Trunc(Sqrt(N)) + 1;
     Y:=1;
     R:=Sqr(Trunc(Sqrt(N))) - N;
     While (R <> 0) Do
      Begin
       R:=R + X;
       X:=X + 2;
       Repeat
        R:=R - Y;
        Y:=Y + 2;
       Until R <= 0;
      End;
     FermaFactorization:=(X - Y) / 2;
    End;
     
    Begin
     Writeln(FermaFactorization(917979909):0:0);
    End.

PS: источник - D.E. Knuth, The Art of Computer Programming, Vol.2]]> tserega Pascal: Математика https://forum.sources.ru/index.php?showtopic=50485&view=findpost&p=332363 Mon, 05 Apr 2004 23:11:35 +0000 Математика https://forum.sources.ru/index.php?showtopic=50485&view=findpost&p=332363 Как проверить простое ли число?
    function isPrime(X: word): boolean;
    var
    i: integer;
    Begin
         isPrime:=false;
         if not odd(x) and (x<>2) { проверяем на чётность  }
              then exit;
         i:=3;
         while i <= sqrt(x) do { проверяем только нечётные }
         begin
              if x mod i = 0 then Exit;
              inc(i,2);
         end;
     
         isPrime:=true;
    End;


Разложение числа на множители
    procedure Factorization(x: word);
    var i: word;
     
     procedure DivX; { делим на простое число, пока делится без остатка }
     begin
          while (x>1) and (x mod i = 0) do
          begin
               write(i:4);
               x:= x div i;
          end;
     end;
     
    begin
         i:=2;
         DivX;
         i:=3;
         while (i < x div 2) do
         begin
               DivX;
               inc(i,2); { <=> i:=i+2; только нечётные числа }
         end;
         if x>1 then writeln(x:4);
    end;


Приближённое представление числа в виде дроби
     
    VAR p,q,qmax:integer;
        d, r, min: real;
    BEGIN
       write('r, qmax=');
       readln(r, qmax); { r - не целое число, qmax - кол-во итераций (циклов) }
       p:=0; q:=1; min:=r;
       REPEAT
         IF p / q < r
              THEN inc(p)
              ELSE inc(q);
         d:=abs(r-p/q);
         IF d < min THEN
         BEGIN
              min:=d;
              writeln(p:7,'/',q)
         END
       UNTIL (q >= qmax) OR (d = 0);
       readln;
    END.


Как работать с отдельными битами?
    FUNCTION IsBitOn (n: word; b : BYTE): BOOLEAN; { Проверяем, установлен ли бит }
    BEGIN
         isBitOn:=((n SHR b) AND 1) = 1
    END;
     
    PROCEDURE SetBitOn (VAR n: Word; b: BYTE); { Устанавливаем бит }
    BEGIN
         N:= N OR (1 SHL b)
    END;
     
    PROCEDURE XORBit (VAR n: Word; b: BYTE); { Переключаем бит }
    BEGIN
         N:= N XOR (1 SHL b) END;
]]> romtek Pascal: Математика https://forum.sources.ru/index.php?showtopic=50485&view=findpost&p=332362 Mon, 05 Apr 2004 23:02:16 +0000 Математика https://forum.sources.ru/index.php?showtopic=50485&view=findpost&p=332362 - Математика и числа -

Чётность/нечётность чисел
    if Odd (Number) then
      writeln (Number, ' нечётно')
    else
      writeln (Number, ' чётно')
или
    if Number and 1 = 0
       then writeln(Number,' чётно')
       else writeln(Number,' нечётно')

Делимость (кратность) чисел
    if Number mod 3 = 0 then
      writeln (Number, ' делится на 3 без остатка');
Делиться без остатка - означает кратность.

Наибольший Общий Делитель (НОД, англ. Greatest Common Divisor)
    { Евклид (Euclidus) }
    function GCD (A: integer;  B: integer): integer;
    begin
        while (a <> 0) and (b <> 0) do
           if a >= b then
             a := a mod b
           else
             b := b mod a;
        GCD := a + b; { один - ноль }
    end;


Наименьшее Общее Кратное (НОК, англ. Least Common Multiplier)
    function LCM (A: integer;  B: integer): integer;
    begin
         LCM := a * b div GCD (a, b)
    end;


Степень
Для целых чисел
    function Power(Base, N: integer): longint;
    { Base - основание , N - степень }
    var
       Result: longint;
       i: word;
    begin
       Result := 1; { придаём начальное значение }
       for i := 1 to N do
         Result := Result * Base;
     
       Power := Result;
    end;


Для вещественных чисел

Возвести A в степень N. Ограничения: только для A > 0
    function PowerExp (A, N: real): real;
    begin
       if A > 0 then
         PowerExp := Exp ( N * Ln (A) )
       else
         PowerExp := 0;
    end;


Факториал ( дополнительная информация: Факториал числа - N! )
    function Factorial(N: word): longint;
    var
       Result: longint;
       i: word;
    begin
       Result := 1;
       for i := 1 to N do
         Result := Result * N;
     
       Power := Result;
    end;


С использованием рекурсии
    function Factorial (N: word): longint;
    begin
       if N = 0 then
         Factorial := 1
       else
         Factorial := N * Factorial (N - 1);
    end;


Вещественный и целый типы
Round - Округляет значение вещественного типа до значения целого типа, округляя.
Trunc - Округляет значение вещественного типа до значения целого типа, отбрасывая дробную часть.
Frac - Возвращает дробную часть аргумента.
Int - Возвращает целую часть аргумента.
       var
           r : real;
         begin
           r := Round ( 123.456);  {    123 }
           r := Round ( 123.778);  {    124 }
           r := Trunc ( 123.456);  {    123 }
           r := Trunc (-123.778);  {   -123 }
           r := Frac  ( 123.456);  {  0.456 }
           r := Int   ( 123.456);  {  123.0 }
           r := Int   (-123.456);  { -123.0 }
         end.


Случайные числа
Процедура Randomize - инициализирует генератор чисел.
Функция Random (N) выдает целочисленные значения в диапазоне от 0 до N-1 !
Например, чтобы сгенерировать число X в диапазоне -N..N , пишем так:
      Randomize;
      X := Random (N + 1) - 2 * N;

Если не написать сначала Randomize; , то будут генерироваться одни и те же числа.]]> romtek Pascal: Математика