de Geoffrey Bourne

Omul care a cunoscut infinitul Codificarea taxiului lui Ramanujan
Ramanujan este în stânga

Omul care a cunoscut infinitul: Codificarea taxiului lui Ramanujan

Ai văzut filmul (sau ai citit cartea) Omul care a cunoscut infinitul?

Acest nou film – în care joacă Dev Patel și Jeremy Irons – explorează matematicianul indian Srinivasa Ramanujan și înțelegerea sa profundă, ingeniozitatea și dragostea pentru matematică.

Filmul m-a inspirat atât la nivel intelectual, cât și emoțional. Dar ceea ce mi-a atras cu adevărat atenția a fost o scenă specială de cinci secunde.

Scena are loc în 1918. Mentorul și prietenul lui Ramanujan, GH Hardy, spune că tocmai luase numărul de taxi 1729 și găsește numărul „unul destul de plictisitor”.

Ramanujan răspunde cu pasiune: „Nu, Hardy, este un număr foarte interesant! Este cel mai mic număr exprimabil ca suma a două cuburi în două moduri diferite. ”

Ramanujan a reușit să vadă dincolo de numărul simplu al taxiului și în adâncurile expresiei din spatele acestuia: a³ + b³ = c³ + d³ … mai cunoscut ca Taxiul lui Ramanujan. Am crezut că această problemă este fascinantă și m-am întrebat cum va arăta implementarea codului. Nu mi-am dat seama că există multe straturi de optimizare pentru acest algoritm de ceapă.

1611067626 780 Omul care a cunoscut infinitul Codificarea taxiului lui Ramanujan
Taxiul pe care l-a luat Ramanujan – cel puțin în film

Prima fisură la implementarea Taxiului lui Ramanujan

Am început cu o implementare directă scrisă în Scala. Codul, cu timpi de performanță, poate fi găsit pe GitHub:

Începem cu o punere în aplicare a forței brute prin looping, deși toate combinațiile, pentru a găsi unde a³ + b³ = c³ + d³. Obținem performanța O (n⁴) datorită celor patru bucle utilizate pentru a calcula toate valorile lui a³, b³, c³ și d³ egale sau mai mici decât parametrul n, care limitează câmpul nostru de căutare.

Această punere în aplicare a forței brute, cu performanță O (n⁴), este cam nesuferită. Deci, cum ne putem descurca mai bine?

Putem face mai bine

Prima întrebare care trebuie pusă este: trebuie întotdeauna să calculăm toate valorile lui a³, b³, c³ și d³? Amintiți-vă, ecuația pe care o folosim este a³ + b³ = c³ + d³. Dacă rezolvăm pentru d³, obținem d³ = a³ + b³ – c³. Astfel, odată ce cunoaștem a³, b³ și c³, putem calcula direct valoarea lui d³ în loc să parcurgem toate valorile lui d³.

Următoarea mea implementare, din nou în Scala, înlocuiește a patra buclă cu calculul d³ = a³ + b³ – c³:

A doua versiune are performanță O (n³), deoarece vom omite bucla finală. Ingrijit!

A treia oară este un farmec

Nu am terminat încă. Există o a treia și cea mai bună îmbunătățire încă de luat în considerare. Ce se întâmplă dacă nu trebuie să rezolvăm toate valorile nu numai ale d³, ci și ale c³? Câteva lucruri de înțeles:

  1. Dacă calculăm toate valorile lui a³ și b³ egale sau mai mici decât n, avem în esență toate valorile posibile nu numai a³ și b³, ci și c³ și d³.
  2. Suma lui a³ + b³ este egală cu suma lui c³ + d³
  3. Dacă suma # 2 de mai sus pentru o pereche dată de numere întregi (a³, b³) se potrivește cu suma unei alte perechi de numere întregi (a³, b³), am găsit în esență perechea c³ și d³.

Dacă stocăm fiecare combinație a sumei a³ + b³ și a perechii corespunzătoare (a³, b³), orice sumă care are două perechi înseamnă că am găsit a³ + b³ = c³ + d³ unde poate fi luată în considerare prima pereche din listă ( a³, b³) și următorul (c³, d³).

De exemplu, dacă iterăm prin combinațiile a³ + b³, vom stoca suma 1729 cu perechea (1³, 12³). Continuând să iterăm, vom vedea o altă sumă de 1729, dar de data aceasta cu perechea (9³, 10³). Deoarece avem două perechi diferite, ambele însumând 1729, am găsit un Taxi Ramanujan care rezolvă pentru a³ + b³ = c³ + d³.

În a treia versiune, folosim un Hashmap pentru a stoca suma (cheia) și lista corespunzătoare de perechi ca set sortat (valoare). Dacă lista conține mai multe perechi, avem un câștigător!

Această implementare are o performanță O (n²), deoarece avem nevoie doar de două bucle pentru a calcula combinațiile pentru a³ și b³. Foarte îngrijite!

Bănuiesc că există o nouă optimizare în care trebuie doar să calculăm valorile lui a³ și să derivăm b³ din a³ (bucla „b” este doar un offset al buclei „a”) cu performanță O (n).

De asemenea, o altă provocare este de a rescrie implementările ca un model funcțional de programare. Voi lăsa asta să o explorezi.

Un film uimitor, un om uimitor

După ce am urmărit Omul care a cunoscut infinitul, am fost înspăimântat de geniul lui Ramanujan. Prin implementarea algoritmului său de taxi – cu mai multe optimizări ale performanței sale – am văzut frumusețea pe care a văzut-o în „Nu, Hardy, este un număr foarte interesant!”

Taxiul lui Ramanujan, vechi de aproape un secol, face încă noi descoperiri. Matematicienii de la Universitatea Emory au găsite numărul 1729 se referă la curbele eliptice și suprafețele K3 – obiecte importante astăzi în teoria corzilor și fizica cuantică.

Mă aștept că am zgâriat doar suprafața numărului de taxi al lui Ramanujan și geniul uimitor al omului.

Despre autor: Geoffrey Bourne este CEO al RETIRĂ – ajutarea persoanelor aflate în pensionare sau în apropierea acesteia să găsească o modalitate mai bună de pensionare.

Mulțumesc pentru lectură!

Dacă v-a plăcut acest articol, nu ezitați să apăsați butonul de batere de mai jos? pentru a-i ajuta pe alții să-l găsească!