Rozkład z użyciem palindromów

 Przy białym tle liczne możliwe literówki. Należy zmienić sposób pisania - nie jestem w stanie wychwycić błedów. 

Zatem matematyka w wersji gry RPG. 

Dostajesz zadanie: sprawdź, czy liczba nieparzysta N jest złożona, pierwsza. Możesz skorzystać z usług NPC, którty jednak ma swoje widzimisię - chce w tablicy umieszczać tylko i wyłacznie palindromy. Zadanie niewykonalne? No dobra, obok palindromu pozwoli umieścić jeszcze jedną wartość, wmawiasz mu, że palindromy wymagają tego dodatkowego argumentu, by znać ich wartość liczbową, bo są 'nad systemem' o podstawie p. Przyjmie to p, choć to duze ustępstwo z jego strony. 

Pierwszy palindrom wpakuj nad systemem binarnym, czyli po jedynce na skraje, zaś do środka połowę z N zmniejszoną o 4+1, czyli pięć. 

 

Teraz proponuję następującą procedurę: bierz palindrom z listy, a przymierzaj się do odłożenia dwu. I to tylko wtedy, gdy środek będzie nieujemy. 

Pierwszy z palindromów powstaje po podwojeniu argumentu p - podstawy systemu. Wyraz najmniej znaczący albo zostanie bez zmian, albo zwiększy się o p, Drugi skrajny podobnie wzrośnie kosztem wyrazu w środku. Palindrom się zachowa.

Z drugim palindromem jest więcej roboty. Zwiększ podstawę p o 1. Najpierw znajdź resztę z dzielenia przez p+1. Suma naprzemienna wyrazów ci pomoże. Postaraj się, by ta reszta c była jak najmniejsza nieujemna, dzieleniem. Teraz masz dwie możliwości, albo odciągniesz od N iloczyn c*(1+p*p) dla wyrazów skrajnych, wtedy środek jest na pewno podzielny przez p+1, i ładuj część całkowitą ilorazu jako środek palindromu.
Drugie podejście, gdy nie chce ci się dzielić tak dużych wartości, jakie mogą się pojawić. Rozbij palindrom na dwa wielomiany. W pierwszy wpakuj z pomocą przeniesień wartości c, 2c, 2c; zaś drugi ma być wielokrotnością p. Nie uzyskasz dokładnej wartości, coś zostanie, jakaś róznica od wyrazu skrajnego z 2c. Pierwszy palindrom podczas konwersji na system o podstawie p+1 przejdzie gładko w palindrom 'c 0 c', zaś z drugiego wielomianu wielokrotność p przekształć w wielokrotność p+1. I tu ta różnica załata powstałą lukę, że utworzą się iloczyn p+1 oraz wartości całkowitej - dodatniej lub ujemnej na wyraz środkowy. 

Gdy środek jest nieujemny, proś o odłożenie do tablicy NPCa. gdy jest ujemny, odrzuć. Gdy wyrazy skrajne się wyzerują, aktualna podstawa p jest dzielnikiem N, co zapamietaj. A kiedy opróżnisz całkowicie tablicę palindromów nie znajdując dzielników, liczba N okaże się pierwsza.

Środki ujemne zaczynają pojawiać się przy podstawach, kiedy liczba może być zapisana jako trójcyfrowa. Wyrazy ujemne przy podwajaniu podstawy jeszcze maleją. Możliwe wzrosty wyrazów skrajnych są przy przechodzeniu na podstawy nieparzyste, przy odpowiednio dużej podstawie p. Kojarzysz, reszty ze wzrostem podstawy utworzą funkcję piłokształtną przedziałami malejącą, zaś długość przedziałów też rośnie z p

Mnożenie Karatsuby i niektóre jego wariacje

W Wikipedii podane jest podejście rekursywne do mnożenia zaproponowane przez Anatolija Karatsubę w postaci dodawania. W pozycji Modern Computer Arithmetic Brenta i Zimmermanna podana jest wersja z odejmowaniem. Jest ona lepsza nie tylko dlatego, że 'unika' bardzo specyficznego błędu przeniesienia przy dodawaniu dużych liczb, nie mieszczących się w rejestrach procesora. Wersja ta ma dodatkowe własności, upraszczające rachunki, co zamierzam pokazać. 

Pozwalam tu sobie na jeszcze inne spojrzenie na to mnożenie. Pierwotnie był podział na dwie części mniej więcej równe, oraz rekursja, gdy wartości były wciąż wielkie. Podstawowym wzorem (dla odejmowania) jest: 

(a*p-b) * (c*p-d) = (ac)*p^2 - (adp+bcp) + (bd) ,

którego składnik -(ad+bc)*p wyraża się jako suma cyfr sąsiednich (ac)+(bd). Przy p=1 mamy wzór dla modyfikacji wartości przy różnych indeksach pozycji cyfr w liczbie. 

Patrząc na to jak na cyfry systemu o podstawie p fragment ten jest współczynnikiem 'cyfry dziesiątek' mnożenia pisemnego.

Przy moim spojrzeniu stosuję podział na n części, których iloczyny mieszczą się w słowie maszynowym. Wtedy rekursja znika. 

W pozycji Brenta, Zimmermanna wprowadza się moduł dla iloczynu różnicy cyfr (a-b)*(c-d). Według mnie znak ten trzeba zachować od początku, licząc na wartosciach ze znakiem signed. Zamiast tego istotna jest kolejność w różnicy - ta nie może ulegać zmianie, np. zawsze odejmując cyfrę na pozycji mniej znaczącej od bardziej znaczącej. 

Przechodzę do wizualizacji mnożenia w systemie o podstawie p. Każdy czynnik A, B ma co najwyżej n niezerowych indeksowanych pozycją wartości, pozostałe są zerami. Dołączam tu także indeksy ujemne.

Iloczyn to wielomian W mający 2n-1 pozycji. Wyznaczam iloczyny cząstkowe A[i]*B[i]. Na poszczególne pozycje wyniku W[k] wpisuję sumę n kolejnych iloczynów A[k-n+1]*B[k-n+1] + ... + A[k]*B[k]. W praktyce większość z tych składników jest zerami, np. na pozycję 0 dostaje się tylko A[0]*B[0],  bo pozostałe to zera o indeksach ujemnych. Sumy te przesuwają się o jednostkę, przez co ich obliczanie praktycznie początkowo narasta o A[i+1]*B[i+1], a po osiągnięciu sumy wszystkich maleje o A[k-n]*B[k-n]. 

Teraz wyznaczam róznice cyfr w obrębie czynników A[j]-A[i], B[j]-B[i], dla wszelkich j>i, które modyfikują wyznaczone wartości wielomianu.
Te różnice też mnożę na wszystkie możliwe sposoby, odejmując wartość na pozycji k=i+j. Ponieważ wartości były ze znakiem, czasem należy je podwójnie odjąć, czyli dodać. 

Ostatnia faza: współczynniki wielomianu nie spełniełniają warunku, by były nieujemne ograniczone z góry przez p. Należy użyć przeniesień jak w drugiej fazie mnożenia pisemnego. 

Dlaczego wersja z odejmowaniem jest lepsza niż z dodawaniem? Wyznaczając kombinację ad+bc podczas dodawania w wielomianie W składniki z takimi samymi indeksami są ujemne dla wyrugowania kombinacji, zaś czasem występują dodatnie, co powoduje mocną szatkownicę znaków, Przy odejmowaniu składniki z takim samym indeksem są zawsze dodatnie i można było użyć wspomnianych przesunięć na jednokrotne obliczanie sum na pozycjach k.

Sposób można takze odwrócić szukajac rozkładu, po zgadnięciu cyfr wyniku sprawdzamy występujące zależności między cyframi.
Przykład: 7387. Z mnożenia Karatsuby w systemie dziesiętnym na najmniej znaczącej pozycji mamy 3*9 = 27. Na pozycji dziesiątek mamy 8-2 = 6.
Wiemy, że na pozycji dziesiątek uzyskamy 27+xy - (9x+3y) przystajace do 7-6 = 1, ten warunek spelnia 8*8 = 64, bo 64+27 = 91.
Suma na pozycji dziesiątek tak wyznaczonych wartości to
8*8+3*9 - (8*9+8*3) = 64+27-(72+24) = 91-96 = -5
Sprawdzamy dla cyfr: 8-9=-1, 8-3=5, (8-9)*(8-3)=-1*5 = -5
Wynik mnożenia 83*89 = 7387