http://en.wikipedia.org/wiki/Binary_GCD_algorithmBinary GCD Algorytm vs. Algorytm Euklidesa na nowoczesnych komputerach
Ten wpis Wikipedia ma bardzo niezadowalające implikację: algorytm Binary GCD był jednocześnie aż 60% bardziej wydajne niż standardowe Euclid algorytmu, ale jak Pod koniec 1998 roku Knuth doszedł do wniosku, że jego współczesne komputery mają tylko 15% wzrost wydajności.
Minęło kolejne 15 lat ... w jaki sposób te dwa algorytmy układają się dzisiaj z postępem w sprzęcie?
Czy Binary GCD nadal przewyższa algorytm Euklidesa w językach niskiego poziomu, ale pozostaje w tyle, ze względu na swoją złożoność w językach wyższych poziomów, takich jak Java? A może różnica zdań w nowoczesnym komputerze?
Dlaczego mnie obchodzi, że możesz zapytać? Tak się składa, że muszę dzisiaj przetworzyć około 100 miliardów takich rzeczy :) Oto toast do życia w erze komputerów (biedny Euclid).
Możesz mieć znak stanowiska do testowania ich, tylko w jednej pętli for (na przykład o wielkości 1000) utwórz listę liczb losowych, a następnie dla wszystkich par liczb obliczyć binarne, aw innej pętli obliczyć euclid gcd, co problem? IMO, nadal w nowoczesnych komputerach binarnych powinien być szybszy specjalnie z większą liczbą. –
Mogłem, a to byłoby dość reprezentatywne dla konkretnego języka na danym procesorze w danym systemie operacyjnym. Jest to dość powszechna operacja numeryczna, z której zaciekawiłem się bardziej ogólnie, jakie jest preferowane rozwiązanie w dzisiejszych aplikacjach o wysokiej wydajności. – jkschneider
Jeśli musisz dziś zrobić 100 miliardów, każda chwila spędzona na debatowaniu nad najskuteczniejszym rozwiązaniem będzie kosztować więcej straconego czasu niż samo wdrożenie jednego lub drugiego. –