(*~\Глагол\Отделы\ЧисАн\64\ц\~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*)
(**)                         ОТДЕЛ шцМатем;
(*============================================================================*
 * НАЗНАЧЕНИЕ: основные математические функции
 *                            для широких целых чисел вида ШИРЦЕЛ - 64 разряда
 *============================================================================*)

ИСПОЛЬЗУЕТ 
  ОС      ИЗ "..\..\..\..\Отделы\Обмен\",
АцМ32     ИЗ "..\..\..\..\Отделы\Заграница\ЧисАн\32\ц\"; (*  АцМ32   - случайные 32-х разрядные целые числа на ASM
                                                          из Асм.отд - бывшие тригонометрия и спец.функции действительных шир.вещ.чисел на ASM *)
(*
АцМ64     ИЗ "..\..\..\..\Отделы\Заграница\ЧисАн\64\ц\"; (*  АцМ64   - случайные 64-х разрядные целые числа на ASM
                                                          из Асм.отд - бывшие тригонометрия и спец.функции действительных шир.вещ.чисел на ASM *)
*)
(*----------------------------------------------------------------------------*
 * Вид, задающий точность вычислений
 *----------------------------------------------------------------------------*)
ВИД
  Цел- = ШИРЦЕЛ;         (* вид Цел - это двойная точность целых - 64 разряда *)

(*----------------------------------------------------------------------------*
 * Машино-зависимые постоянные
 *----------------------------------------------------------------------------*)
ПОСТ
  МаксЦел- = МАКС(Цел);
                            (* ШИРЦЕЛ в диапазоне [-(2^63);     +(2^63 -1) ]  *)
(*----------------------------------------------------------------------------*
 * Постоянные для ЦОС
 *----------------------------------------------------------------------------*)
ПОСТ
  ДваВстеп1- =   2;     (*   один бит  *)
  ДваВстеп2- =   4;     (*    два бита *)
  ДваВстеп3- =   8;     (*    три бита *)
  ДваВстеп4- =  16;     (* четыре бита *)
  ДваВстеп5- =  32;     (*   пять бит  *)
  ДваВстеп6- =  64;     (*  шесть бит  *)
  ДваВстеп7- = 128;     (*   семь бит  *)
  ДваВстеп8- = 256;     (* восемь бит  *)
  ДваВстеп9- = 512;     (* девять бит  *)
  ДваВстеп10- =  1024;  (*       десять битов *)
  ДваВстеп11- =  2048;  (*  одиннадцать битов *)
  ДваВстеп12- =  4096;  (*   двенадцать битов *)
  ДваВстеп13- =  8192;  (*   тринадцать битов *)
  ДваВстеп14- = 16384;  (* четырнадцать битов *)
  ДваВстеп15- = 32768;  (*   пятнадцать битов *)
  ДваВстеп16- = 65536;  (*  шестнадцать битов *)

  ДваВстеп17- =  131072;  (*   семнадцать битов *)
  ДваВстеп18- =  262144;  (* восемнадцать битов *)
  ДваВстеп19- =  524288;  (* девятнадцать битов *)
  ДваВстеп20- = 1048576;    (*  20 битов *)
  ДваВстеп21- = 2097152;    (*  21 бит   *)
  ДваВстеп22- = 4194304;    (*  22 бита *)
  ДваВстеп23- = 8388608;    (*  23 бита *)

  ДваВстеп24- = 16777216;   (*  24 бита *)
  ДваВстеп25- = 33554432;   (*  25 бит  *)
  ДваВстеп26- = 67108864;   (*  26 бит  *)

  ДваВстеп27- = 134217728;  (*  27 бит  *)
  ДваВстеп28- = 268435456;  (*  28 бит  *)
  ДваВстеп29- = 536870912;  (*  29 бит  *)
  ДваВстеп30- =1073741824;  (*  30 бит  *)
  ДваВстеп31- =2147483648;  (*  31 бит  *)


(*-оооооооооооооо- опережающие определения/заготовки задач -ооооооооооооооооо-*)


(*----------------------------------------------------------------------------*
 * Мин, макс, знак шир.целого числа и обмен 2-х шир.целых чисел
 *----------------------------------------------------------------------------*)

ЗАДАЧА^ мин-(x,y:Цел):Цел;
ЗАДАЧА^ макс-(x,y:Цел):Цел;          

ЗАДАЧА^ знакЧ-(x:Цел):Цел;     
ЗАДАЧА^ условСменаЗнакаЧ-(x,y:Цел):Цел;  (* x*знакЧ(y) *)
                                                  
ЗАДАЧА^ обмен-(x+,y+:Цел);
                                  

(*----------------------------------------------------------------------------*
 * Основные математические функции для шир.целых чисел
 *----------------------------------------------------------------------------*)

ЗАДАЧА^ кв-(x:Цел):Цел;


(*----------------------------------------------------------------------------*
 * Степенные функции и целые показатели степени
 *----------------------------------------------------------------------------*)

ЗАДАЧА^ степЦЦ-(x-:Цел; n-:ЦЕЛ):Цел;  (* шир.целая положит.степ. x^n (n=>0)
                                                              #0 шир.целого x *)
ЗАДАЧА^ показательСтепениДвойки-(N:Цел):ЦЕЛ;
(* Цель:  найти такой целый <показательСтепениДвойки>, что
 *  шир.целое <N> = 2^<показательСтепениДвойки>
 *)
ЗАДАЧА^ Степень2-(n-:ЦЕЛ):Цел;(* шир.целая положит.степень 2^n (n=>0) числа 2 *)
(* Вычисление  2^n  с помощью умножений шир.целых, где n=>0 *)


(*----------------------------------------------------------------------------*
 * Источники случайных шир.целых чисел
 *----------------------------------------------------------------------------*)

ЗАДАЧА^ случ0-(цСлучайное:ЦЕЛ);    (* выставка начального состояния 32-х разрядного *)
ЗАДАЧА^ случЦ-():Цел;              (* шир.целые от -(2^63) до +(2^63 -1) *)



(*=рррррррррррррррррррррррр= реализация задач =рррррррррррррррррррррррррррррр=*)


(*============================================================================*
 * Мин, макс, знак шир.целого числа и обмен 2-х шир.целых чисел
 *============================================================================*)

(*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*)
ЗАДАЧА мин-(x,y:Цел):Цел;
УКАЗ
  ЕСЛИ x < y ТО
    ВОЗВРАТ x
  ИНАЧЕ
    ВОЗВРАТ y
  КОН
КОН мин;

(*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*)
ЗАДАЧА макс-(x,y:Цел):Цел;
УКАЗ
  ЕСЛИ x > y ТО
    ВОЗВРАТ x
  ИНАЧЕ
    ВОЗВРАТ y
  КОН
КОН макс;

(*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*)
ЗАДАЧА знакЧ-(x:Цел):Цел;
УКАЗ
  ЕСЛИ x >= 0 ТО
    ВОЗВРАТ  1
  ИНАЧЕ
    ВОЗВРАТ -1
 КОН
КОН знакЧ;

(*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*)
ЗАДАЧА условСменаЗнакаЧ-(x,y:Цел):Цел;
УКАЗ
  ЕСЛИ y < 0 ТО
    ВОЗВРАТ -МОДУЛЬ(x)
  ИНАЧЕ
    ВОЗВРАТ  МОДУЛЬ(x)
  КОН
КОН условСменаЗнакаЧ;

(*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*)
ЗАДАЧА обмен-(x+,y+:Цел);
ПЕР
  врем:Цел;
УКАЗ
  врем:=x;
  x:=y;
  y:=врем
КОН обмен;


(*============================================================================*
 * Основные математические функции для шир.целых чисел
 *============================================================================*)

(*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*)
ЗАДАЧА кв-(x:Цел):Цел;
УКАЗ
(*Матем.код:=0;*)
  ВОЗВРАТ x*x
КОН кв;


(*============================================================================*
 * Степенные функции и целые показатели степени
 *============================================================================*)

(*---------------------------------------- локальная для шцМатем.отд ---------*)
ЗАДАЧА пробаСтеп(x,y,отв+:Цел):КЛЮЧ;
(*
   Проверка случаев x=0, y=0 и y=1.
   В этих случаях результат x^y см. в <отв+>
 *)
УКАЗ
(*
  дМатем.код:=0;
*)
  ЕСЛИ x = 0 ТО
    ЕСЛИ y = 0 ТО     (* 0^0 = lim  x^x = 1 *)
      отв:=1          (*       x->0         *)
    АЕСЛИ y > 0 ТО
      отв:=0          (* 0^y = 0 *)
(*
    ИНАЧЕ
      дМатем.код:=дМатем.ОСОБЕННОСТЬ;
             отв:=шцМатем.МаксЦел
*)
    КОН;
    ВОЗВРАТ ВКЛ
  АЕСЛИ y = 0 ТО
    отв:=1;           (* x^0 = 1 *)
    ВОЗВРАТ ВКЛ
  АЕСЛИ y = 1 ТО
    отв:=x;           (* x^1 = x *)
    ВОЗВРАТ ВКЛ
  ИНАЧЕ
    ВОЗВРАТ ОТКЛ
  КОН
КОН пробаСтеп;

(*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*)
ЗАДАЧА степЦЦ-(x-:Цел; n-:ЦЕЛ):Цел;     (* шир.целая положит.степ. x^n (n=>0) *)
(*                                                            #0 шир.целого x
 * Вычисление  x^n  с помощью умножений шир.целых, где n=>0, x#0
 *)
ПЕР
  y,m,ответ:Цел;
УКАЗ
                                                 (*- проверка особых случаев -*)
  ЕСЛИ пробаСтеп(x,n,ответ) ТО
    ВОЗВРАТ ответ
  КОН;
                                    (*- вычисление шир.целой степени в цикле -*)
  y:=x;                  (* сохраняем x *)
  m:=n;                  (* сохраняем n *)
      ответ:=1;                             (* для накопления целых умножений *)
  ПОКА 1 < m ВЫП (* при больших m это быстрее,
                                               чем последовательные умножения *)
    ЕСЛИ НЕ ЧЕТ(m) ТО
      ответ:=ответ*y
    КОН;

    y:=шцМатем.кв(y);    (* y:=y*y; - затирание y *)   
    m:=m ДЕЛИТЬ 2        (* m:=m/2; - затирание m *)   
  КОН;
      ответ:=ответ*y;    (* m=1 *)

    ВОЗВРАТ  ответ
КОН степЦЦ;

(*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*)
ЗАДАЧА показательСтепениДвойки-(N:Цел):ЦЕЛ;
(*
 * Цель:  найти такой целый <показательСтепениДвойки>, что
 *  шир.целое <N> = 2^<показательСтепениДвойки>
 *---------------------------------------------------------------------------- 
 * Ответ: <показательСтепениДвойки> в диапазоне [0..63] или -1, если ответа не существует
 *)
ПЕР
                биты:Цел;
  показательСтепени2:ЦЕЛ;
УКАЗ
(*
              показательСтепени2:=0;
  ПОКА ЧЕТ(N) ВЫП
    N := N ДЕЛИТЬ 2;
    УВЕЛИЧИТЬ(показательСтепени2)  (* подсчёт числа множителей 2 в
         N=2^<показательСтепени2> пока не настанет N=0, т.е. N станет нечётно *)
  КОН;
  ЕСЛИ N # 1 ТО 
    показательСтепени2:=-1 (* -1,
         если нет равенства (т.е. не существует) 2^<показательСтепени2> = <N> *)
  КОН;
*)
  ВЫБРАТЬ УЗК(N) ИЗ
  |ДваВстеп1: показательСтепени2:= 1;   (* N=   2;          один бит  *)
  |ДваВстеп2: показательСтепени2:= 2;   (* N=   4;           два бита *)
  |ДваВстеп3: показательСтепени2:= 3;   (* N=   8;           три бита *)
  |ДваВстеп4: показательСтепени2:= 4;   (* N=  16;        четыре бита *)
  |ДваВстеп5: показательСтепени2:= 5;   (* N=  32;          пять бит  *)
(*
  |ДваВстеп6: показательСтепени2:= 6;   (* N=  64;         шесть бит  *)
  |ДваВстеп7: показательСтепени2:= 7;   (* N= 128;          семь бит  *)
  |ДваВстеп8: показательСтепени2:= 8;   (* N= 256;        восемь бит  *)
  |ДваВстеп9: показательСтепени2:= 9;   (* N= 512;        девять бит  *)
  |ДваВстеп10: показательСтепени2:=10;  (* N=       1024;      десять битов *)
  |ДваВстеп11: показательСтепени2:=11;  (* N=       2048; одиннадцать битов *)
  |ДваВстеп12: показательСтепени2:=12;  (* N=       4096;  двенадцать битов *)
  |ДваВстеп13: показательСтепени2:=13;  (* N=       8192;  тринадцать битов *)
  |ДваВстеп14: показательСтепени2:=14;  (* N=      16384;четырнадцать битов *)
  |ДваВстеп15: показательСтепени2:=15;  (* N=      32768;  пятнадцать битов *)
  |ДваВстеп16: показательСтепени2:=16;  (* N=      65536; шестнадцать битов *)
  |ДваВстеп17: показательСтепени2:=17;  (* N=     131072;  семнадцать битов *)
  |ДваВстеп18: показательСтепени2:=18;  (* N=     262144;восемнадцать битов *)
  |ДваВстеп19: показательСтепени2:=19;  (* N=     524288;девятнадцать битов *)
  |ДваВстеп20: показательСтепени2:=20;  (* N=    1048576;    20 битов *)
  |ДваВстеп21: показательСтепени2:=21;  (* N=    2097152;    21 бит   *)
  |ДваВстеп22: показательСтепени2:=22;  (* N=    4194304;    22 бита  *)
  |ДваВстеп23: показательСтепени2:=23;  (* N=    8388608;    23 бита  *)
  |ДваВстеп24: показательСтепени2:=24;  (* N=   16777216;    24 бита  *)
  |ДваВстеп25: показательСтепени2:=25;  (* N=   33554432;    25 бит   *)
  |ДваВстеп26: показательСтепени2:=26;  (* N=   67108864;    26 бит   *)
  |ДваВстеп27: показательСтепени2:=27;  (* N=  134217728;    27 бит   *)
  |ДваВстеп28: показательСтепени2:=28;  (* N=  268435456;    28 бит   *)
  |ДваВстеп29: показательСтепени2:=29;  (* N=  536870912;    29 бит   *)
  |ДваВстеп30: показательСтепени2:=30;  (* N= 1073741824;    30 бит   *)
  |ДваВстеп31: показательСтепени2:=31;  (* N= 2147483648;    31 бит   *)
*)
  ИНАЧЕ
               показательСтепени2:=63;
     (*
                  биты := 2^63;  
      *)
                  биты := МАКС(Цел);
(*     -(2^63) <= биты <= +(2^63 -1 ) = МАКС(Цел)        *)

                         (* половиним <биты> до меньше N *)
    ПОКА биты > N ВЫП
(*
                   подбор <показательСтепени2> делением (!) на 2, т.е.
   уменьшением от 63 до 2^<показательСтепени2> = N
 *)
      УМЕНЬШИТЬ(показательСтепени2);
         биты := биты ДЕЛИТЬ 2      (* биты -> N=2^<показательСтепени2> *)
    КОН;
(*
               показательСтепени2:=-1 (* -1,
         если нет равенства (т.е. не существует) 2^<показательСтепени2> = <N> *)
*)
  КОН;
  ВОЗВРАТ      показательСтепени2
(*.=>
   ...или...медленный Log2(N)...подбором 
(*
    Логарифм по основанию 2 (округляется до ниже следующего
    целого значения в случае, когда N не является степенью 2)
    Результат будет в диапазоне [ 0..63 ]
 *)
ПЕР
  биты,
  показательСтепени2:ЦЕЛ;
УКАЗ
               показательСтепени2:=63;
(*
       биты := 2^63 -1;  
 *)
       биты := МАКС(ШИРЦЕЛ);

(* половиним <биты> до равенства (или меньше) N *)
  ПОКА биты > N ВЫП
(*     подбор <показательСтепени2> делением (!) на 2, т.е.
   уменьшением от 63 до 2^<показательСтепени2> = N *)

    УМЕНЬШИТЬ (показательСтепени2);
       биты := биты ДЕЛИТЬ 2;  (* биты -> N=2^<показательСтепени2> *)
  КОН;
  ВОЗВРАТ      показательСтепени2
<=.*)
КОН показательСтепениДвойки;

(*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*)
ЗАДАЧА Степень2-(n-:ЦЕЛ):Цел; (* шир.целая положит.степень 2^n (n=>0) числа 2 *)
(*
 * Вычисление  2^n  с помощью умножений шир.целых, где n=>0
 *)
ПЕР
  y,m,ответ:Цел;
УКАЗ
  ВЫБРАТЬ n ИЗ
  | 0:  ответ:=          1;  (*        один бит    *)
  | 1:  ответ:=          2;  (*        один бит    *)
  | 2:  ответ:=          4;  (*         два бита   *)
  | 3:  ответ:=          8;  (*         три бита   *)
  | 4:  ответ:=         16;  (*      четыре бита   *)
  | 5:  ответ:=         32;  (*        пять бит    *)
  | 6:  ответ:=         64;  (*        шесть бит   *)
  | 7:  ответ:=        128;  (*         семь бит   *)
  | 8:  ответ:=        256;  (*       восемь бит   *)
  | 9:  ответ:=        512;  (*       девять бит   *)
  | 10: ответ:=       1024;  (*       десять битов *)
  | 11: ответ:=       2048;  (*  одиннадцать битов *)
  | 12: ответ:=       4096;  (*   двенадцать битов *)
  | 13: ответ:=       8192;  (*   тринадцать битов *)
  | 14: ответ:=      16384;  (* четырнадцать битов *)
  | 15: ответ:=      32768;  (*   пятнадцать битов *)
  | 16: ответ:=      65536;  (*  шестнадцать битов *)
  | 17: ответ:=     131072;  (*   семнадцать битов *)
  | 18: ответ:=     262144;  (* восемнадцать битов *)
  | 19: ответ:=     524288;  (* девятнадцать битов *)
  | 20: ответ:=    1048576;  (*           20 битов *)
(*
  | 21: ответ:=    2097152;  (*           21 бит   *)
  | 22: ответ:=    4194304;  (*           22 бита  *)
  | 23: ответ:=    8388608;  (*           23 бита  *)
  | 24: ответ:=   16777216;  (*           24 бита  *)
  | 25: ответ:=   33554432;  (*           25 бит   *)
  | 26: ответ:=   67108864;  (*           26 бит   *)
  | 27: ответ:=  134217728;  (*           27 бит   *)
  | 28: ответ:=  268435456;  (*           28 бит   *)
  | 29: ответ:=  536870912;  (*           29 бит   *)
  | 30: ответ:= 1073741824;  (*           30 бит   *)
  | 31: ответ:= 2147483648;  (*           31 бит   *)
*)
  ИНАЧЕ                                   (* вычисление целой степени в цикле *)
    y:=2;             (* сохраняем 2 в y *)
    m:=n;             (* сохраняем n     *)
        ответ:=1;                           (* для накопления целых умножений *)
    ПОКА 1 < m ВЫП (* при больших m это быстрее,
                                               чем последовательные умножения *)
      ЕСЛИ НЕ ЧЕТ(m) ТО  (*     y= 2,   4,     16,      256. /   65536.       *)
        ответ:=ответ*y   (* ответ= 1,                   256. /                *)
      КОН;               (*     y= 4,  16,    256,    65536, / 2^24*2^24 - переполнение *)
                         (*     m=24,    12,      6,       3./     1.         *)
      y:=шцМатем.кв(y);  (* y:=y*y; - затирание y *)   
      m:=m ДЕЛИТЬ 2      (* m:=m/2; - затирание m *)   
    КОН;
        ответ:=ответ*y   (*                        m=1, 256*65536 = 16777216. *)
  КОН;

  ВОЗВРАТ ответ
КОН Степень2;


(*============================================================================*
 * Источники/генераторы случайных шир.целых чисел
 *============================================================================*)

(*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*)
ЗАДАЧА случ0-(цСлучайное:ЦЕЛ);  (* выставка начального состояния 32-х битного *)
(*
 * Установка/Выставка источника случ.шир.целых чисел в начальное состояние
 *)
УКАЗ

  АцМ32.СлучНач(цСлучайное)   (* выставка в нач.состояние генер.случ. 32-х разрядных целых *)

КОН случ0;

(*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*)
ЗАДАЧА случЦ-():Цел;                    (* шир.целые от -(2^63) до +(2^63 -1) *)
(*
 * Возвращает шир.целые случайные числа             из [-(2^63);   +(2^63 -1)]
 *)
УКАЗ

  ВОЗВРАТ АцМ32.СлучЦел()               (* шир.целое от -(2^63) до +(2^63 -1) *)

КОН случЦ;

(*-ssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss-*)
УКАЗ
  случ0(ОС.ВремяТекущее())    (* установка в нач.состояние генер.сл.шир.целых *)
(*случ0(ОС.Время())*)         (* установка в нач.состояние генер.сл.шир.целых *)
КОН шцМатем.
