Sierpiński w swojej monografii "Co wiemy, a czego nie wiemy o liczbach pierwszych" wspomniał kilkakrotnie o wartości 2^{101}. Jest to liczba 101-bitowa, która oparła się próbom faktoryzacji przedwojennych matematyków. Dowiedziano się tylko, że jest złożona.
Heksadecymalnie ma ona wartość 0x1F,FFFF,FFFF,FFFF,FFFF,FFFF,FFFF.
Rozłożona została przez Cuningham Project, w którym podano rozkład, dwa dzielniki, oba mają kilkanaście cyfr, zaś sama liczba ma ich 31. W dodatku nie są bardzo bliskie siebie. Iloraz dzielników ma około pięciu cyfr dziesiętnych.
Zastanowiło mnie, czy moje algorytmy poradzą sobie z nią i przygotowałem liczbę do faktoryzacji pod najszybszy z nich. Zajęło mi to kilka dni.
Mam teraz do czynienia z liczbami mającymi piętnaście cyfr dziesiętnych (51 bitów). Lecz zastanawiam się ze startem.
Mianowicie czasem mylę się przy dodawaniu, a przy takich wartościach nie jestem w stanie przetestować poprawności wyniku.
Dalej, mam do sprawdzenia gigantyczną krotność postaci, są to setki biliardów, czyli 7e14.
Wyliczyłem, że w niektórych iteracjach mogę sobie darować nawet miliony przypadków, przeskakując podstawy, przy których najmniej znacząca cyfra tworzy ciąg, który mogę jawnie podać za pomocą równania kwadratowego. Lecz dla tego równania kwadratowego ze względu na wielkość współczynników nie mam gwarancji poprawnego rozwiązania.
Potrzebne jest wsparcie pewnego typu interaktywnego programu komputerowego, którego brak nakłonił mnie do szukania algorytmów publikowanych w tym blogu. Programu, który nie zawsze liczy, ale prezentuje wartości pośrednie, oczywiście z dopasowaną pode mnie grafiką.
Wracając jeszcze do obliczeń, do przygotowanie zastosowałem algorytm publikowany tutaj 5.11.2012 "Pierwiastek kwadratowy przy systemach niedziesiątkowych".
http://matformac.blogspot.com/search/label/pierwiastek%20kwadratowy
Kiedy miałem blisko połowy cyfr znaczących pierwiastka, każdy kolejny iloraz był coraz bliższy podstawie potęgi 2, którą w danym kroku używałem. Po przekroczeniu połowy cyfr znaczących, każdy kolejny iloraz był dokładnie potęgą 2. Zatem połowę dzieleń można było zastąpić mnożeniem przez odpowiednią potęgę 2.
W dodatku, rachując w systemie szesnastkowym lub binarnym, podczas obliczeń część bitów z początku lub końca liczb nie była ruszana. Bity te były po prostu kopiowane. Pozwoliło to utworzyć 'ramkę' długości do 52 bitów, wewnątrz której były przeprowadzane obliczenia. Z jednym wyjątkiem - przeniesienie, gdy pierwsza cyfra ramki była maksymalną wartością.
Ostatecznie operacje mnożenia i dzielenia sprowadzały się do działań z argumentami będącymi liczbami nie większymi niż pierwiastek czwartego stopnia liczby rozkładanej lub potęgach 2.
Brak komentarzy:
Prześlij komentarz