P-АДИЧЕСКИЕ ЧИСЛА

https://gamedev.ru/flame/forum/?id=277298

Бог создал целые числа, всё остальное — дело рук человека.
© Леопольд Кронекер

Оказывается не так давно по историческим меркам математики придумали сабж и он изумителен.
Буква p вообще в названии от слова prime, т.е. "простые", но проще объяснять на десятичной записи (сразу замечу, что она не попадает под определение, но уже содержит важные свойства).
Такие числа выглядят как обычные целые/натуральные числа но содержат бесконечно большое число цифр влево. Любое целое может быть превращено в p-адическое просто добавлением слева бесконечного числа нулей. Но в p-адических эта бесконечность принципиальна (в то время как у целых наоборот принципиальна конечность записи и смысла).
Какие последствия для математических практик это несёт? Давайте проверим.
Попробуем вычесть из нуля единицу (0-1=?).
При вычете первого разряда получается 9 и заём, заём переходит во второй разряд и далее процесс никогда не останавливается - получается число
...999999999999999999999999999.
Замечу, что принципиально важно, что справа число кончается в конкретном месте, но слева у него бесконечная цепь девяток.
И это ровно то что есть -1.
Если мы попробуем добавить к ...999 единицу, то опять же за счёт переполнений получим 0. p-адический ноль это бесконечная цепь нулей - всё как по определению.
То есть эти числа просто ведут себя как табло калькулятора но в котором бесконечное число разрядов.
...998 - это -2.
...997 - это -3.
И так далее. Да да да, это представление отрицательных в int как есть. :lol:

Попробуем проверить этот неоспоримый факт с другой стороны.
Если ...999 умножить на 10, то получиться ...990. Добавим к результату 9 и получим снова ...999.
То есть
...999*10 + 9 = ...999
заменим ...9 на переменную x и выразим её значение формулой:
x*10 + 9 = x
10x - x = -9
9x=-9
x=-1
Срослось! Всё так и есть - ...999 и в арифметике и в формулах есть ничто иное как минус один!

А что если мы возьмём число не из всех девяток, а из всех единиц?
Давайте попробуем провернуть с ним такой же фокус:
...111*10 + 1 = ...111
10*x + 1= x
10*x - x = -1
x*9 = -1
x = -1/9 = ...99999999999999999999999999/9=...111111111111111111111111 Так стоп! У нас получилось мало того, что отрицательное, но еще и дробное число! -1/9!

Тут уже зададимся следующим упражнением для ума - попробуем решить как бы задачку из книжки головоломок - вывести такое 10-адическое число которое при умножении на число 7 (...0007) в результате даст в разрядах ровно ...001.
Это забавное упражнение из загадок если вы его решите подведет вас к периодическому числу следующей структуры:
...(285714)3.
Т.е. в начале числа стоит тройка, а потом бесконечно повторяется фрагмент 285714. Вот можете в калькуляторе умножать сколько угодно разрядов такого числа на 7 и увидите, что за вычетом первой цифры (из-за "недоубегания" в бесконечность) в разрядах будет получаться ...0000000000000000000000000000000000000000000000000000000001.
Сколько периодов вобьёте - столько нулей и будет.
А для адических как мы помним разрядов бесконечно и полученное число в точности равно 1.
А какое число при умножении на семь даёт в результате 1?
Это 1/7.
Бгха!

И это конечно удивительно - получается, что p-адические числа основываясь на одном только принципе записи чисел точно так же как в обычных целых числах тем не менее лёгким проворотом ума покрыли этим одновременно и отрицательные числа и дробные числа - революции которые древние математики совершали со скрипом и огромными усилиями. А тут это просто данность из коробки.
При этом последнее что надо заметить, что на базе десятичной системы исчисления можно сделать совсем абсурдное - подобрать такое число которое будет квадратом самого себя и не равно 0 или 1. Но это проблема именно десятиричной системы исчисления, когда базис на котором основана запись числа неоднозначно разлагается на множители. Тогда в задачках типа как мы выше подбирали разряды для умножения на 7 возникают неоднозначности и это очень плохо для математической строгости.
Поэтому истинные p-адические должны быть базированы на системе исчисления с базисом в простом числе - например двоичные или троичные числа могут быть базисом для истинных p-адических. А примеры выше я просто привёл для наглядности.

Итак, двоичная система исчисления как раз подходит для p-адических и (1)1 в двоичной системе является минус единицей, что любой продвинутый программист знает из практики данной в ощущениях чисел со знаком дополнения до двух.
То есть int всю жизнь был p-адическим числом в котором предполагается, что последний разряд копируется на бесконечное продолжение числа и по свойствам и по характеристикам.
Вот правда дробные числа в конечное число знаков не пролазит, т.к. требует зацикленного продолжения некоего паттерна в бесконечность.
А так же это означает, что ряд 1+2+4+8+16+32+... равен минус единице.
И если будете выбирать другие системы исчисления, то можете получить много много других дробей того, что является геометрическим расходящимся рядом в классической математике из школы.

 

Для тех кому интересно поковыряться в p-адических написал функцию на C++17 которая переводит рациональную дробь a/b в строку с точным представлением p-адического для основания p. Напоминаю, что основаниями должны быть простые числа - хотя можно скармливать, например, 10-тичную систему, но для неё алгоритм весьма часто даёт сбой и не может определить даже первую цифру адического представления, о чём сообщает в результате-строке.
Так же налабал немного дополнительного кода и программа ниже просит ввести числители и знаменатели двух целых чисел (в числителе можно вводить отрицательное число чтобы дробь была отрицательной) и выводит их сумму в p-адическом представлении.
Представление имеет следующую структуру: (периодическая часть)начало/порядок
Любые компоненты кроме периодической части могут отсутствовать.
Например в 10-адической (9) это бесконечность девяток (минус 1), а (9)0 это нуль за которым идёт бесконечная цепь девяток (минус 10).
В некоторых случаях возникает компонента "порядок" - это десятичное число означающее на сколько разрядов надо перенести точку-разделитель целой и дробной части влево (если отрицательно) или вправо (если положительно).
Например
(0)1/-2 это на самом деле (0).01 - одна сотая здесь нужно перенести точку-разделитель на два разряда влево.

Код (C++):

1. #include <iostream>
2. #include <vector>
3. #include <string>
4. #include <numeric>
5.  
6. char num_to_digit(int num)
7. {
8.    if ( num <= 9 )
9.      return '0' + num;
10.    else
11.      return 'A' + num - 10;
12. }
13.  
14. std::string rational_to_p_adic( int p, long long a, long long b )
15. {
16.    std::string ret;
17.    int rep_index = -1;
18.    std::vector<int> hist_k;
19.    std::vector<long long> hist_a;
20.    int order = 0;
21.  
22.    long long divisor = std::gcd(a, b);
23.    a /= divisor;
24.    b /= divisor;
25.  
26.    while ( (a % p) == 0 )
27.    {
28.      a /= p;
29.      order += 1;
30.    }
31.  
32.    while ( (b % p) == 0 )
33.    {
34.      b /= p;
35.      order -= 1;
36.    }
37.  
38.    while ( true )
39.    {
40.      bool found = false;
41.      bool hist_found = false;
42.      for ( int k = 0; k < p; k++ )
43.      {
44.        if ( (a - b * k) % p == 0 )
45.        {
46.          found = true;
47.          a = (a - b * k) / p;
48.          // try to find in history
49.          for ( int j = hist_k.size() - 1; j >= 0; j-- )
50.          {
51.            if ( (hist_k[j] == k) && (hist_a[j] == a) )
52.            {
53.              hist_found = true;
54.              rep_index = j;
55.              break;
56.            };
57.          };
58.          if ( !hist_found )
59.          {
60.            hist_k.push_back(k);
61.            hist_a.push_back(a);
62.          };
63.          break;
64.        };
65.      }
66.      if ( !found )
67.      {
68.        return std::string( "digit not found at iter " ) + std::to_string(hist_k.size()) + ", a: " + std::to_string(a);
69.      };
70.      if ( hist_found )
71.        break;
72.    };
73.    if ( rep_index != -1 )
74.    {
75.      ret = "(";
76.      for ( int i = hist_k.size() - 1; i >= rep_index; i-- )
77.        ret.push_back(num_to_digit(hist_k[i]));
78.      ret.push_back(')');
79.    }
80.    for ( int i = rep_index - 1; i >= 0; i-- )
81.      ret.push_back(num_to_digit(hist_k[i]));
82.  
83.    if ( order != 0 )
84.      ret += std::string("/") + std::to_string(order);
85.  
86.    return ret;
87. };
88.  
89. class Rational
90. {
91. public:
92.    long long num, den;
93.    Rational(): num(0), den(1) {};
94.    Rational( long long aNum, long long aDen ): num(aNum), den(aDen)
95.    {
96.      normalize();
97.    };
98.    void normalize()
99.    {
100.      long long divisor = std::gcd(num, den);
101.      num /= divisor;
102.      den /= divisor;
103.    }
104.    std::string asAdic(int power)
105.    {
106.      return rational_to_p_adic(power, num, den);
107.    };
108.    void input(const char *name)
109.    {
110.      std::cout << name << " numerator: ";
111.      std::cin >> num;
112.      std::cout << name << " denominator: ";
113.      std::cin >> den;
114.    };
115.    void output(const char *name, int power)
116.    {
117.      std::cout << name << " " << num << "/" << den << " " << asAdic(power) << "\n";
118.    };
119.    Rational operator+(const Rational &rhs)
120.    {
121.      Rational ret(num * rhs.den + rhs.num * den, den * rhs.den);
122.      ret.normalize();
123.      return ret;
124.    };
125. };
126.  
127. int main()
128. {
129.    int power = 7;
130.    Rational a, b;
131.    a.input("a");
132.    b.input("b");
133.    Rational c = a + b;
134.    a.output("", power);
135.    std::cout << "+\n";
136.    b.output("", power);
137.    std::cout << "=\n";
138.    c.output("", power);
139.    //for ( int i = 1; i <= 100; i++ )
140.    //   std::cout << "1/" << i << " = " << rational_to_p_adic(10, 1, i) << "\n";
141. }

И для непосредственного разглядывания из любопытства приведу первую сотню 7-адических обратных чисел (т.е. 1 делить на целое число):

Код (Text):

1. 1/1 = (0)1
2. 1/2 = (3)4
3. 1/3 = (4)5
4. 1/4 = (15)2
5. 1/5 = (2541)3
6. 1/6 = (5)6
7. 1/7 = (0)1/-1
8. 1/8 = (06)1
9. 1/9 = (361)4
10. 1/10 = (4620)5
11. 1/11 = (1623550431)2
12. 1/12 = (26)3
13. 1/13 = (563142103524)6
14. 1/14 = (3)4/-1
15. 1/15 = (0635)1
16. 1/16 = (36)4
17. 1/17 = (4640552320261143)5
18. 1/18 = (164)2
19. 1/19 = (264)3
20. 1/20 = (5643)6
21. 1/21 = (4)5/-1
22. 1/22 = (0645260214)1
23. 1/23 = (3646041553230206251134)4
24. 1/24 = (46)5
25. 1/25 = (1650)2
26. 1/26 = (265054401612)3
27. 1/27 = (565120342)6
28. 1/28 = (15)2/-1
29. 1/29 = (0652113)1
30. 1/30 = (3652)4
31. 1/31 = (465263560451232)5
32. 1/32 = (1653)2
33. 1/33 = (2653414610)3
34. 1/34 = (5653624510130421)6
35. 1/35 = (2541)3/-1
36. 1/36 = (065432)1
37. 1/37 = (365450520)4
38. 1/38 = (465)5
39. 1/39 = (165513023406)2
40. 1/40 = (2655)3
41. 1/41 = (5655430340453146441610112363262135202250)6
42. 1/42 = (5)6/-1
43. 1/43 = (065601)1
44. 1/44 = (3656130105)4
45. 1/45 = (465624340211)5
46. 1/46 = (1656354261450103124052)2
47. 1/47 = (26564625544214316360513)3
48. 1/48 = (56)6
49. 1/49 = (0)1/-2
50. 1/50 = (0660)1
51. 1/51 = (3660163104542513)4
52. 1/52 = (466025534304)5
53. 1/53 = (16603461311215006320535545)2
54. 1/54 = (266043521)3
55. 1/55 = (56605226330244651345)6
56. 1/56 = (06)1/-1
57. 1/57 = (066)1
58. 1/58 = (3661041)4
59. 1/59 = (46611206433625634513540144250)5
60. 1/60 = (1661)2
61. 1/61 = (266124322031330455110141502260400542344635336211556525164406)3
62. 1/62 = (566131630224114)6
63. 1/63 = (361)4/-1
64. 1/64 = (06614325)1
65. 1/65 = (366150300516)4
66. 1/66 = (4661542303)5
67. 1/67 = (166161102123360263225513653522042500505564543306403441153013144624)2
68. 1/68 = (2661645603413544)3
69. 1/69 = (5662012641054524315033)6
70. 1/70 = (4620)5/-1
71. 1/71 = (0662111654223641450613231526463356260045550124430252160534351402033104)1
72. 1/72 = (366214)4
73. 1/73 = (466220524060200446142606)5
74. 1/74 = (166223610)2
75. 1/75 = (2662)3
76. 1/76 = (566232)6
77. 1/77 = (1623550431)2/-1
78. 1/78 = (066241345203)1
79. 1/79 = (366244152556362016011453312206126316434300422514110304650655213354460540350232)4
80. 1/80 = (4662)5
81. 1/81 = (166252335421504560644030113)2
82. 1/82 = (2662550153561423220640041165131052434460)3
83. 1/83 = (56626033536514134246145436104502644320111)6
84. 1/84 = (26)3/-1
85. 1/85 = (0662651615453022)1
86. 1/86 = (366300)4
87. 1/87 = (4663025)5
88. 1/88 = (1663050036)2
89. 1/89 = (2663101046454042555122342165230320602516133140035656202126241115443245014363460641505335)3
90. 1/90 = (566312153440)6
91. 1/91 = (563142103524)6/-1
92. 1/92 = (0663162130560035045361)1
93. 1/93 = (366321164615055)4
94. 1/94 = (46632312622105506530241)5
95. 1/95 = (166325040612)2
96. 1/96 = (2663)3
97. 1/97 = (566331506030134154254623114053616432144221104020100335160636532512412043552613050234522445562646)6
98. 1/98 = (3)4/-2
99. 1/99 = (066335142454411262023215603650)1
100. 1/100 = (3663)4