[Algorytmy] czy liczba jest kwadratem liczby naturalnej
[Algorytmy] czy liczba jest kwadratem liczby naturalnej
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.
Ostatnio zmieniony 19 cze 2019, o 14:21 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
- Użytkownik
- Posty: 65
- Rejestracja: 4 mar 2014, o 00:32
- Płeć: Mężczyzna
- Lokalizacja: VBATools | Kraków | Poland | Europe | Earth | SolSystem | SomewareInSpace
- Podziękował: 1 raz
- Pomógł: 7 razy
[Algorytmy] czy liczba jest kwadratem liczby naturalnej
w VBA (czyli w Excelu) można to obliczyć nast sposób:
Wynikiem czego funkcja zwraca błąd jeśli nie jest to liczba naturalna
Można tez obliczyć jaka wartość dane podział takiego działania
Po wklejeniu kodów w moduł, użycie w arkuszu:
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
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
[Algorytmy] czy liczba jest kwadratem liczby naturalnej
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.
-
- Użytkownik
- Posty: 65
- Rejestracja: 4 mar 2014, o 00:32
- Płeć: Mężczyzna
- Lokalizacja: VBATools | Kraków | Poland | Europe | Earth | SolSystem | SomewareInSpace
- Podziękował: 1 raz
- Pomógł: 7 razy
[Algorytmy] czy liczba jest kwadratem liczby naturalnej
tak?...
p.s.
Mariusz wg ustawień forum jesteś kobietą!
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
Mariusz wg ustawień forum jesteś kobietą!
[Algorytmy] czy liczba jest kwadratem liczby naturalnej
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.
-
- Użytkownik
- Posty: 65
- Rejestracja: 4 mar 2014, o 00:32
- Płeć: Mężczyzna
- Lokalizacja: VBATools | Kraków | Poland | Europe | Earth | SolSystem | SomewareInSpace
- Podziękował: 1 raz
- Pomógł: 7 razy
[Algorytmy] czy liczba jest kwadratem liczby naturalnej
Zmienne tylu LongLong masz w .Net'cie
Masz Visual Studio - pobierz sobie triala albo wersje Express i działaj.
Masz Visual Studio - pobierz sobie triala albo wersje Express i działaj.
- kerajs
- Użytkownik
- Posty: 8581
- Rejestracja: 17 maja 2013, o 10:23
- Płeć: Mężczyzna
- Podziękował: 307 razy
- Pomógł: 3349 razy
[Algorytmy] czy liczba jest kwadratem liczby naturalnej
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}\)
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}\)
Ostatnio zmieniony 19 cze 2019, o 19:09 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
[Algorytmy] czy liczba jest kwadratem liczby naturalnej
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
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ę:
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
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.
Przetestuj taki program
Kod: Zaznacz cały
int main()
{
float a = 248248248248248248248;
float b = a/2;
printf("%f",b);
}
Kod: Zaznacz cały
int main()
{
float a = 248248248248248248248.0;
float b = a/2;
printf("%f",b);
}
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);
}
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.