[Algorytmy] czy liczba jest kwadratem liczby naturalnej

[MariuszJ]

Potrzebuje szybki algorytm który określa dla bardzo dużych liczb, mających co najmniej dwadzieścia cyfr, czy ta liczba jest kwadratem liczby naturalnej. Pierwiastkowanie najlepiej wykluczyć albo użyć go jedynie pomocniczo, bo dla tak dużych liczb pierwiastek będzie liczbą przybliżoną rzeczywistą i mnie zmyli że ta liczba nie jest poszukiwaną. Chyba najlepszą prostą metoda jest poszukiwanie połówkowe. W ten sposób będę testował kolejne liczby naturalne poprzez ich kwadrat, czy dostałem liczbę początkową. Problemem jest tylko to, jaki zakres min i maks wybrać dla tego poszukiwania połówkowego, żeby było jak najmniej operacji.

[OShon]

w VBA (czyli w Excelu) można to obliczyć nast sposób:

Kod: Zaznacz cały

Function kwadrat(lliczba As Double) As Boolean
Dim liczb As Double
liczb = VBA.Sqr(lliczba)
If liczb = liczb  1 Then kwadrat = True Else kwadrat = False
End Function

Wynikiem czego funkcja zwraca błąd jeśli nie jest to liczba naturalna

Można tez obliczyć jaka wartość dane podział takiego działania

Kod: Zaznacz cały

Function NthRoot(dblNumber As Double, lngRoot As Long) As Double
    NthRoot = dblNumber ^ (1 / lngRoot)
End Function

Po wklejeniu kodów w moduł, użycie w arkuszu:

AU

f421a39bf5033dffmed.png (8.72 KiB) Przejrzano 370 razy

[MariuszJ]

To nie będzie działać dla liczb 30 cyfrowych bo pierwiastek zaokrągli się dużo więcej niż o jedynkę w porównaniu do wartości rzeczywistej.

[OShon]

tak?...

Kod: Zaznacz cały

Sub test()
Dim l As Double, ll As Double
l = CDbl("12345678912346789123456789")
ll = NthRoot(l, 2)
Debug.Print l & " = " & ll & " " & kwadrat(ll)
End Sub

p.s.
Mariusz wg ustawień forum jesteś kobietą!

[MariuszJ]

Na pewno bym nie liczył na to że olbrzymia liczba pierwiastkowana która ma kwadrat naturalny da mi wynik pierwiastka taki jaki jest rzeczywiście. Pierwiastkowanie to jest liczenie sumy szeregu i wyrażenie ma wartość rzeczywistą. Przy dużych liczbach przybliżenie będzie duże. Nie można liczyć na to że to zadziała. Liczby mogą być na granicy int64 a w dalszych zastosowaniach będę musiał użyć biblioteki do obsługi ogromnych liczb, stucyfrowych. Najprostszy pomysł to jest wybranie zakresu min maks zbliżonego do pierwiastka i przeszukiwanie połówkowe w tym zakresie dla sprawdzenia czy a*a=sprawdzana liczba. Trzeba tylko określić w miarę nieduży zakres, który na pewno zawiera pierwiastek.

[OShon]

Zmienne tylu LongLong masz w .Net'cie
Masz Visual Studio - pobierz sobie triala albo wersje Express i działaj.

[kerajs]

Zupełnie się nie znam na potrzebnych algorytmach, ale warto wprowadzić prosty warunek wstępny. Kwadraty dzielone przez \(\displaystyle{ 4}\) dają resztę \(\displaystyle{ 0}\) lub \(\displaystyle{ 1}\). Sprowadza się to do sprawdzenia jaką resztę dostanie się z dwóch ostatnich cyfr modulo \(\displaystyle{ 4}\).

Przykład:

\(\displaystyle{ 11223126623546745672513467245923675678657812364650137456022 \\
123545679856334896389204398698765489056891634789561896439765089 \\
126504736701607234560796497569127348659625696582789436457634567 \\
9134896789152734879873456987948365786734867187177787754564}\)

z tych czterech od razu można odrzucić pierwszą i trzecią bo:
\(\displaystyle{ 22 \mod 4 =2 \\
67 \mod 4 =3}\)

[Dudenzz]

Przy dużych liczbach to nie jest takie proste. Nie wiem czy zdajesz sobie sprawę, ale największa liczba całkowita, zapisana na 4 bajtach (int) to około \(\displaystyle{ 2 \cdot 10^9}\), tymczasem największa liczba zmiennoprzecinkowa zapisana na 4 bajtach (float) to około \(\displaystyle{ 3 \cdot 10^{38}}\). Na pierwszy rzut oka wydaje się to nielogiczne, ale w gruncie rzeczy jest całkiem proste. Otóż duży zakres wynika ze sposobu reprezentacji liczby - floaty zapisane są w postaci wykładniczej, a inty wprost. Co za tym idzie, duży zakres obarczony jest sporym błędem, błąd (absolutna wartość błędu) jest tym większy, im większa liczba jest reprezentowana.

Przetestuj taki program

Kod: Zaznacz cały

int main()
{
        float a = 248248248248248248248;
        float b = a/2;
        printf("%f",b);
}

Program nie powinien się w ogóle skompilować, ponieważ liczba \(\displaystyle{ 248248248248248248248}\) jest liczbą całkowitą. Program "nie wie", że chcesz ją zapisać jako float, a konwersja byłaby wykonana dopiero po przypisaniu liczby do zmiennej. Liczby zmiennoprzecinkowe muszą mieć "." w zapisie. W związku z tym wprowadź poprawkę:

Kod: Zaznacz cały

int main()
{
        float a = 248248248248248248248.0;
        float b = a/2;
        printf("%f",b);
}

Program skompiluje się, float ma większy zakres niż int, ale po uruchomieniu programu otrzymasz \(\displaystyle{ 124124122746330284032.000000}\), czego (błędu) można było się spodziewać.

Korzystając z kalkulatora wielkich liczb (wygoogluj taki kalkulator online) przeprowadź kilka testów korzystając z kodu

Kod: Zaznacz cały

#include <iostream>
#include <cmath>
int main()
{
        float a = 15159303447561417273129.0;
        float b = sqrt(a);
        printf("%f",b);
}

Zauważysz, że dla dużych liczb wynik jest zawsze całkowity. Wynika to oczywiście z błędu precyzji. Mimo to, możesz wykorzystać wnioski analizy do zbudowania proponowanego przez ciebie zakresu poszukiwań.

Innym, mniej praktycznym, ale o lepszym podłożu teoretycznym sposobem wyznaczania takiego zakresu jest wykorzystanie metody Newtona-Raphsona do poszukiwania przybliżonego pierwiastka z liczby.