[Algorytm] Odwracanie elementów w większym pierścieniu z użyciem rozszerzonego algorytmu Euklidesa

Mateusz Kowalski
Autor Wideo Bloga Matematycznego
www.kowalskimat...

[@holyshit922]

Mateusz plus za sposób przedstawienia algorytmu Euklidesa Przedstawiłeś ten algorytm w sposób wg którego łatwo i efektywnie można go zapisać w ulubionym języku programowania Widziałem inny sposób przedstawienia tego algorytmu i aby zapisać tamten sposób trzeba było ilorazy zapamiętać na stosie Twój sposób przedstawienia tego algorytmu jest bardziej efektywny Jako ćwiczenie możecie zapisać algorytm Euklidesa w ulubionym języku programowania bazując na tym co nakręcił Mateusz Tutaj zależnie od danych wejściowych współczynniki są albo w xa oraz ya albo w xb oraz yb Pisząc program dobrze by było aby były w jednej parze zmiennych no ale to można zrealizować jedną instrukcją if oraz zamianą elementów

[@martebest]

Gratuluję błyskotliwego umysłu. Sprawnie zrobiony wykład. Lubię rozkminiać takie mądre algorytmy. Euklides to był błyskotliwy umysł. Szkoda, że Grecja nie ma obecnie tak znamienitych matematyków.

[@geemkii]

Łatwo i przyjemnie. Dlaczego tu jest tylko 7 komentarzy? Pewnie dla tego, że trafiają tu leniwi ludzie, którzy chcą szybko zrozumieć temat bez wysiłku. Dziękuję za wytłumaczenie.

[@holyshit922]

Innym sposobem znajdowania odwrotności jest wykorzystanie twierdzenia Eulera uogólniającego Małe twierdzenie Fermata

[@97kos]

Czy można postąpić szybciej z tymi odwracalnymi, żeby nie szukać po kolei, tylko do pary dawać, np. jak już znaleźliśmy 1, to 59 też jest, jak 7, to 53 itp.? (suma ich wynosi 60)

[@kowalskimateusz]

Dobre pytanie, odpowiedź tak, dowód: Niech a będzie odwrotnością b, tzn. ab=1 przemnażając przez -1 dostaniemy -ab=-1. zachodzi 60a=0. te dwie kongruencje można dodać stronami wówczas 60a-ba = -1, czyli (60-b)a=-1 ponownie przemnóżmy przez -1 wówczas (60-b)(-a)=1. c.n.d Oczywiście zamiast 60 może być dowolnie m. przyjąłem 60 dla ustalenia uwagi.

[@geemkii]

chyba mały błąd w minucie 10.50. Rozpisując tabelę Z8 numerujemy chyba 0 do 7.

[@remiastro1584]

Gdzie moznabyloby wykorzystać tą wiedzę w praktyce? Jak zwykle bardzo dobry film

[@sebastiankrupa135]

Kodowanie metodą Rabina

[@hue1980]

na kolokwium

[@pawechosta3835]

Ciekawe

[@holyshit922]

No to jak wyglądałby kod tej funkcji nwd ? int gcdex(int a,int b, int &x,int &y){ int xa = 1, ya = 0, xb = 0, yb=1; int a0 = a, b0 = b; int q; while(a0 != 0 && b0 != 0) { if(abs(a0) > abs(b0)) { q = a0/b0; a0 = a0 % b0; xa -= q*xb; ya -= q*yb; } else { q = b0/a0; b0 = b0 % a0; xb -= q*xa; yb -= q*ya; } } if(b0 == 0) { x = xa; y = ya; } else { x = xb; y = yb; } if(a*x+b*y < 0) { x = -x; y = -y; } return a*x+b*y; } Teraz chyba funkcja będzie działać poprawnie

[@martebest]

Też lubię język C. Napisałem dwa algorytmy z wykorzystaniem biblioteki mpfr do obliczania liczby Pi. Jeden nazwałem FCPI, a drugi PILL. FCPI wykorzystuje złotą liczbę Phi i liczby Fibonacciego, a PILL, to rozszerzony algorytm Leibniza.