Wyobraź sobie, że rozumiesz algorytm na tyle dobrze, że możesz go wykonać - ręcznie - z pamięci - i bez zapamiętywania jakichkolwiek nienaturalnych sztuczek Książka ZK znów się rozrosła, tym razem, aby nauczyć Szybkiej Transformacji Fouriera -- a konkretnie Transformacji Teoretycznej Liczb (NTT). Algorytm NTT ocenia wielomian w n punktach w czasie O(n log n). Zwykle taka ocena zajmowałaby czas O(n²). Chociaż Szybka Transformacja Fouriera ma już liczne zasoby edukacyjne, uznaliśmy je za niezadowalające. Na przykład, bardzo powszechne wyjaśnienie opiera się na "dzieleniu wielomianu na parzyste i nieparzyste składniki," używając "współczynników twiddle" i "motyli." Jednak te metody wydają się być przypadkowymi odkryciami, które opisują algorytm, a nie wyjaśniają go. Uważamy, że takie cechy wymienione powyżej są przypadkowe w porównaniu do głębszych -- i znacznie łatwiejszych do zrozumienia -- podstawowych koncepcji. Idziemy nawet tak daleko, aby unikać analogii do liczb zespolonych. Zadbaliśmy o to, aby każdy krok w podróży edukacyjnej był uzasadniony i aby każdy krok był trywialnym rozszerzeniem poprzedniego. Dlatego nie ma skoków koncepcyjnych ani zaskakujących odkryć. Nie pozwól, aby nazwy rozdziałów cię przestraszyły; podstawowe zasady to tylko podstawowa algebra. Na koniec 13 rozdziałów będziesz w stanie obliczyć Transformację Teoretyczną Liczb ręcznie! Link następny.