Jaki jest skuteczny algorytm znajdowania pierwiastka kwadratowego liczby całkowitej z bardzo dużej liczby, cyfra po cyfrze?

Potrzebuję napisać program, aby znaleźć całkowity pierwiastek kwadratowy z liczby, która ma tysiące cyfr. Nie mogę używać Newtona Raphsona, ponieważ nie mam typów danych do przechowywania i dzielenia tak dużych liczb. Używam długiej tablicy w C do przechowywania numeru. Czy istnieje algorytm znajdowania pierwiastka kwadratowego przez może iterowanie po cyfrach?Jaki jest skuteczny algorytm znajdowania pierwiastka kwadratowego liczby całkowitej z bardzo dużej liczby, cyfra po cyfrze?

Edit:

Nie mogę korzystać z zewnętrznej biblioteki jak GMP.

Źródło

2014-05-25 Naman

See [wikipedia] (http://en.wikipedia.org/wiki/Methods_of_computing_square_roots). –

@alexvii Podana tam metoda dziesiętnej bazy wymaga znalezienia x (20 * p + x), ale ponieważ moja cyfra jest bardzo duża, p również będzie duże i obliczanie takiej wartości może być bardzo powolne. Zastanawiałem się, czy istnieje jakakolwiek metoda, która nie wymagałaby mnożenia tak dużych liczb. – Naman

Czy możesz zabrać zewnętrzne biblioteki? Ponieważ [Biblioteka wielowymiarowa arytmetyczna GNU] (https://gmplib.org/), między innymi. –

Możesz zastosować metodę podziału na długi, aby obliczyć pierwiastek kwadratowy, który jest nauczany w szkole. Możesz zaimplementować tę metodę dla podstawy 10, a wynik jest obliczany cyfra po cyfrze od lewej do prawej. Możesz zatrzymać się, gdy obliczona zostanie liczba całkowita.

Calculation of squareroot

Źródło

2014-05-25 13:57:59

Próbowałem tej metody, ale problemem jest to, że dzielnik staje się coraz większy. A jeśli moja dana liczba ma tysiąc cyfr, dzielenie i znajdowanie reszty będzie bardzo trudne. – Naman

Możesz zapisywać liczby w c-stringach (tablice znaków kończą się znakiem "NUL") i wykonywać arytmetycznie tak, jak robimy to na papierach. Napisałem [ten przykład] (http://codepad.org/T2AcSJzN) lata temu dla dodawania i mnożenia. Stopniowo dodawałem funkcjonalności i zmniejszałem czas poświęcony dzięki profilowaniu, a po kilku miesiącach znalazłem efektywną bibliotekę dużych liczb. Jeśli nie chcesz używać biblioteki dużej liczby całkowitej innej firmy, napisz ją dla siebie używając podstawowych pojęć arytmetycznych i spraw, aby była wytrzymała i wydajna. –

Do tej metody potrzebne są tylko operacje mnożenia i odejmowania. –

Jeśli możesz wprowadzić numer docelowy, musisz musi mieć mieć sposób na przechowywanie co najmniej jednego tak dużego numeru. W przypadku Newtona-Raphsona wystarczy, że będziesz w stanie zmniejszyć o połowę i dodać liczby. Pomyśl o sposobie zmniejszenia o połowę liczby bez użycia podziału.

ETA: Korekta: można uniknąć dzielenia poprzez podwojenie i odejmowanie.

Źródło

2014-05-25 13:36:26 rossum

Jak korzystać z Newtona-Raphsona bez dzielenia? Iteracja to 'x '= (x + S/x)/2', która polega na obliczaniu' S/x' za każdym razem (jak również dodawanie i zmniejszanie o połowę). – rici

Nie możesz zrobić Newtona Raphsona bez podziału. To, o czym wspomniałeś, to metoda Binary Search. Ale tam też będę musiał sprawdzić, czy moja szacunkowa liczba jest poprawna, poprzez podniesienie jej do kwadratu i porównanie z podaną liczbą, co jest trudnym zadaniem z bardzo dużymi liczbami. – Naman

Dzięki za poprawkę. Odpowiedź zmieniona. – rossum

Wydaje się, że wiele bardzo nierealistyczne ograniczeń na swoim „” bignum realizacji. Mogę zasugerować wyszukiwanie binarne? Przy każdej iteracji znajdź wartość "w połowie" mid = (hi + lo)/2 i przyciń przestrzeń przeszukiwania jako [hi, mid] lub [mid, lo] w zależności od kwadratu tych wartości.

nie tak szybko, jak NR, etc. Ale powinien zbiegać ze starannej obróbce kwadratury wartości zakresu ...

Źródło

2014-05-25 16:29:01

Jaki jest skuteczny algorytm znajdowania pierwiastka kwadratowego liczby całkowitej z bardzo dużej liczby, cyfra po cyfrze?

Odpowiedz

Powiązane problemy