[Ardeo]

Jak może wyglądać algorytm, który zwróci mi skrócony licznik i mianownik podanego ułamka f(x) = [licznik, mianownik]? Przykładowo: f(0.25) = [1, 4], f(3/9) = [1, 3].
Znalazłem proste algorytmy mnożące podaną liczbę *10, aż zniknie wartość po przecinku, a następnie szukające GCD, ale one nie działają dla ułamków okresowych link.

Są do tego biblioteki (link i link), ale czy ktoś wie jak one działają?

#programowanie #matematyka

[deryt]

Jak może wyglądać algorytm

@Ardeo:
Po pierwsze powiedz w jakim języku programowania, bo w wielu są różne funkcje które robią to od ręki ( ͡° ͜ʖ ͡°)

Ja bym to zrobił tak:
tablica z liczbami pierwszymi. Ja bym zaimplementował takową z pierwszą setką liczb pierwszych, jeśli będą potrzebne kolejne, to pod-algorytm który ją powiększa do pożądanego rozmiaru za pomocą sita E. (używając wcześniejszych znanych wartości).
Licznik i

[tyrytyty]

@Ardeo: ale jak podajesz na wejściu 3/9 to nie podajesz faktycznie 0.(3) tylko jakiś skończony ułamek który jest przybliżeniem tego. Jedynym sposobem by móc na wejsciu podać dowolny ułamek jest podawanie licznika i mianownika oddzielnie, a wtedy problem zawsze sprowadza się do znalezienia GCD.

[deryt]

@deryt:
Optymalizacja:
1. w moim algorytmie funkcja min() jest wykorzystywana wielokrotnie, przy liczbach ogromnych - dużą ilość razy. Można to obejść robiąc algorytm dla licznikwhile ( i < sqrt(licznik) ){...
zamiast tego stosuj:

set ograniczenie=sqrt(licznik)

while( i < ograniczenie) ){...

dzięki czemu funkcja sqrt zostanie wywołana tylko raz, a nie tysiące razy (przy liczbach rzędu milionów).
Co prawda współczesne kompilatory są w stanie taki błąd wyłapać i naprawić (trzymać w pamięci

[Ardeo]

@tyrytyty: to jest słuszna uwaga, że na komputerze w sumie nie ma ułamków nieskończonych. Ale to by oznaczało, że wyznaczenie M i L z liczby 3/9 może się odbyć tylko metodą, która je jakoś jedynie przybliży do oczekiwanych z pewną granicą błędu, nie?

@deryt: chodzi mi o pseudo kod. W Twojej propozycji też wydaje mi się, że pasowało by dodać jakiś parametr, który nam ograniczy głębię w jaką taki algorytm

[koostosh]

@Ardeo: rozwinięcie w ułamek łańcuchowy to jest to czego pewnie szukasz

[tyrytyty]

@koostosh: na stackoverflow o tym wspomnieli

https://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree

[deryt]

@Ardeo:
Mój algorytm działa wyłącznie dla ułamków n/m dla n,m całkowitych.
Dla ułamków podanych dziesiętnie nie ma to sensu.
Po pierwsze 0.3 w pamięci taki ułamek w zależności od typu albo jest równy 0.3, albo jeśli jest przechowywany binarnie to:
.01001100110011001100110011001100110011110011001100110011, co nie jest dokładnie 0.3, tylko 0.29999999999999.
Po drugie mój algorytm się NIE zapętli, bo nie ma takiej możliwości. Tylko że dla 0.33333 poda ci ułamek 33333/10000, bo tyle ta

[sezzart]

@Ardeo: Diophantine approximation. Możesz uprecyzowac nawet dokładność

[Chodok]

@Ardeo: A ja znalazłbym Najmniejszy Wspólny Dzielnik a potem podzielił te liczby przez niego

[Chodok]

@Chodok: Edit największy