Uprzejmie prosze o pomoc (reszta z dzielenia)

[Nothingman]

Witam!

Czy byly mi ktos w stanie pomoc i powiedziec jak obliczyc reszte z dzelenia:
1111^4444 przez 21...


Pozdrawiam i z gory dziekuje
Nothingman

[Gik]

Post by Nothingman
1111^4444 przez 21...

To musisz sobie przeczytac coś na temat dzielenia modulo.
Poniżej masz wykorzystanie tej metody

1111 mod 21 = 19 lub -2 !

4444 = 4 * 11 * 101

(-2)^4 mod 21 = 16 lub -5
(-5)^11 mod 21 = 4
4^ 101 mod 21 = 16 ( to może być trudne !! to moze inaczej)
101 = 10*10 +1
4^10 mod 21 = 4
4^10 mod 21 = 4
4 * (4 mod 21) = 4 * 4 = 16 ( no to juz było bardzo łatwe)

czyli 1111^4444 mod 21 = 16
Poszukiwana reszta to 16. Liczba 1111^4444 ma 13 536 cyfr

[qfel]

Alternatywnie
1111^0 mod 21 = 1
1111^1 mod 21 = 19
1111^2 mod 21 = 4
1111^3 mod 21 = 13
1111^4 mod 21 = 16
1111^5 mod 21 = 10
1111^6 mod 21 = 1 (tak jak 1111^0)
Czyli mamy 6 - elementowy cykl.
4444 mod 6 = 4, czyli wynik to 16 (liczymy od zera)

[Gik]

Post by qfel
Alternatywnie
1111^0 mod 21 = 1
1111^1 mod 21 = 19
1111^2 mod 21 = 4
1111^3 mod 21 = 13
1111^4 mod 21 = 16
1111^5 mod 21 = 10
1111^6 mod 21 = 1 (tak jak 1111^0)
Czyli mamy 6 - elementowy cykl.
4444 mod 6 = 4, czyli wynik to 16 (liczymy od zera)

Brawo!
Wykorzystanie cykli to już wyższy stopień umiejętności (być może
nieosiągalny dla autora pytania).
Jedynie co można by dodać to nieco inne obliczenie długości cyklu bo
obliczenie 1111^6 {19 cyfr} mod 21 nie jest trywialne, a gdy długość
cyklu będzie dłuższa to będzie to nieco kłopotliwe.

tak dla treningu proponuję obliczyć resztę z dzielenia

12345678910^12345678910 przez 47

albo jeszcze lepiej przez 173 :)

[Maciek]

Post by Gik

Post by qfel
Alternatywnie
1111^0 mod 21 = 1
1111^1 mod 21 = 19
(...........)
1111^6 mod 21 = 1 (tak jak 1111^0)
Czyli mamy 6 - elementowy cykl.

Brawo!
Wykorzystanie cykli to już wyższy stopień umiejętności
(być może nieosiągalny dla autora pytania).
Jedynie co można by dodać to nieco inne obliczenie długości
cyklu bo obliczenie 1111^6 {19 cyfr} mod 21 nie jest trywialne,

Etam, nigdzie tu nie ma 19 cyfr, bo wcale nie potrzeba
podnosić 1111 do szóstej potęgi! Przecież każdą kolejną
resztę można policzyć z poprzedniej. Wychodzą rachunki
na liczbach trzycyfrowych, nie więcej. :-)
Trywialne to może nie jest, ale wcale nie bardzo trudne.

Post by Gik
a gdy długość cyklu będzie dłuższa to będzie to nieco kłopotliwe.
tak dla treningu proponuję obliczyć resztę z dzielenia
12345678910^12345678910 przez 47
albo jeszcze lepiej przez 173 :)

No, to jeszcze da się zrobić "na piechotę", ręcznie.
Przecież log_2(12345678910) to tylko 33 z małym hakiem. :)


Maciek

[Gik]

Post by Maciek

Post by Gik
Jedynie co można by dodać to nieco inne obliczenie długości
cyklu bo obliczenie 1111^6 {19 cyfr} mod 21 nie jest trywialne,

Etam, nigdzie tu nie ma 19 cyfr, bo wcale nie potrzeba
podnosić 1111 do szóstej potęgi! Przecież każdą kolejną
resztę można policzyć z poprzedniej. Wychodzą rachunki
na liczbach trzycyfrowych, nie więcej. :-)

Napisałem 'by dodac nieco inne obliczenie'. Ty napisałeś bardzo
lakonicznie ale poprawnie jak to zrobić.

Post by Maciek

Post by Gik
tak dla treningu proponuję obliczyć resztę z dzielenia
12345678910^12345678910 przez 47
albo jeszcze lepiej przez 173 :)

No, to jeszcze da się zrobić "na piechotę", ręcznie.
Przecież log_2(12345678910) to tylko 33 z małym hakiem. :)

I słusznie tutaj są do obliczenia ' po drodze' tylko liczby conajwyżej 4
lub 5-cyfrowe.
'Ręcznie' to może w obecnych czasach już nie, ale na pewno wystarczą
prymitywne narzędzia matematyczne np Excel (nie używam, ale w z
przeszłości pamiętam, że taki problem to nie 'problem')

Pozostanie jednak 'dla treningu proponuję obliczyć resztę z dzielenia
......'
Może jednak Maciek lub qfel skusi się na odpowiedż na to pytanie

[p***@dionizos.zind.ikem.pwr.wroc.pl]

Post by Gik

Post by Maciek

Post by Gik
tak dla treningu proponuję obliczyć resztę z dzielenia
12345678910^12345678910 przez 47
albo jeszcze lepiej przez 173 :)

No, to jeszcze da się zrobić "na piechotę", ręcznie.
Przecież log_2(12345678910) to tylko 33 z małym hakiem. :)

I słusznie tutaj są do obliczenia ' po drodze' tylko liczby conajwyżej 4
lub 5-cyfrowe.
'Ręcznie' to może w obecnych czasach już nie, ale na pewno wystarczą
prymitywne narzędzia matematyczne np Excel (nie używam, ale w z
przeszłości pamiętam, że taki problem to nie 'problem')
Pozostanie jednak 'dla treningu proponuję obliczyć resztę z dzielenia
......'
Może jednak Maciek lub qfel skusi się na odpowiedż na to pytanie

Metodę ręcznego postępowania podałeś w pierszym liście - OK.

Ale po co uprawiać sadyzm? Trze wziąć taki kalkulator jak pari/gp ;)

? #
timer = 1 (on)
? Mod(12345678910,47)^12345678910
time = 0 ms.
%10 = Mod(14, 47)
? Mod(12345678910,173)^12345678910
time = 0 ms.
%11 = Mod(150, 173)
?

[Maciek]

Post by Maciek

(....................)
tak dla treningu proponuję obliczyć resztę z dzielenia
12345678910^12345678910 przez 47
albo jeszcze lepiej przez 173 :)

No, to jeszcze da się zrobić "na piechotę", ręcznie.
Przecież log_2(12345678910) to tylko 33 z małym hakiem. :)

(.......)
'Ręcznie' to może w obecnych czasach już nie, (...)

"W obecnych czasach już nie"? A dlaczegóż to?
Czy współcześnie nie umiemy już pisemnie liczyć?


Wczoraj przez chwilę (hm, powiedzmy ;)) nie miałem
ciekawszych zajęć (hm, powiedzmy ;)) i porachowałem.

12345678910 ^ 12345678910 = 14 (mod 47)
12345678910 ^ 12345678910 = 150 (mod 173)

Narzędzia: kartka, pisak i czterodziałaniowy kalkulator.

Zajęło jakieś 3 godziny (pisemne przeliczenie wykładnika
na zapis dwójkowy, z dwiema pomyłkami - około pół godziny;
dzielenie pisemne podstawy przez 47 i 173 w celu znalezienia
reszt, w tym trzy pomyłki - około kwadransa; wyznaczenie
pierwszej reszty z potęgi - około godziny; wyznaczenie
drugiej reszty, z jedną pomyłką - niecałe półtorej h).

Gdyby nie kalkulator, zajęłoby to pewnie cały dzień,
bo trzebaby jeszcze pisemnie wykonywać obliczenia
w rodzaju: 156*156*145 mod 173 --> 39, co nawet
po redukcji do postaci (-17)*(-17)*(-28) wymaga
kilku działań na liczbach trzy- lub czterocyfrowych.
A obliczeń takich wyszłoby po 34 na każde z dwu zadań...


Dziś sprawdziłem wynik arkuszem kalkulacyjnym. Zgadza się.
Czas - ok. 10 minut.


Maciek

[Gik]

Post by Maciek

Post by Maciek

(....................)
tak dla treningu proponuję obliczyć resztę z dzielenia
12345678910^12345678910 przez 47
albo jeszcze lepiej przez 173 :)

No, to jeszcze da się zrobić "na piechotę", ręcznie.
Przecież log_2(12345678910) to tylko 33 z małym hakiem. :)

'Ręcznie' to może w obecnych czasach już nie, (...)

"W obecnych czasach już nie"? A dlaczegóż to?
Czy współcześnie nie umiemy już pisemnie liczyć?

Z tego co obserwuję na codzień to twoje pokolenie już nie umie liczyć
pisemnie. A że Ty jesteś wyjątkiem to potwierdza to tylko regułę.

Post by Maciek
Wczoraj ....... porachowałem.
12345678910 ^ 12345678910 = 14 (mod 47)
12345678910 ^ 12345678910 = 150 (mod 173)

Brawo, bezbłędnie !!.

Post by Maciek
Narzędzia: kartka, pisak i czterodziałaniowy kalkulator.
Zajęło jakieś 3 godziny (pisemne przeliczenie wykładnika
na zapis dwójkowy, z dwiema pomyłkami - około pół godziny;

......
gratuluję samozaparcia.

Post by Maciek
Dziś sprawdziłem wynik arkuszem kalkulacyjnym. Zgadza się.
Czas - ok. 10 minut.

I oto mi chodziło pisząc "ale na pewno wystarczą prymitywne narzędzia
matematyczne np Excel ". Szybko i skutecznie.

Liczba M = 12345678910 ^ 12345678910
posiada 135 802 468 010 cyfr dziesiętnych. Gdyby cyfry miały 4 mm
szerokości to zapis tej liczby był długości 543 210 km ( dalej niż na
księzyc).
Liczba M jest tak wielka, że nie ma tyle atomów w całym wszechwświecie.
Nawet gdyby cały wszechświat był wypełniony tylko neutrinani, jeden obok
drugiego, to też byłoby ich mniej. Musielibyśmy stworzyć miliony
nadświatów (neutrino kolejnego wszechświatu bylby całym wszechświatem
poprzednim) oraz miliony podświatów.

Oczywiście liczby M nie mozna zapisać jawnie w żadnym komputerze. Mimmo
to udało się Maćkowi policzyć resztę z dzielenia tej niewyobrażalnie
dużej liczby przez 47 i 173.

No cóż w niektórych dziedzinach matematyki można sięgać bardzo daleko. W
innych niestety nie, np napewno nie uda się stwierdzić, czy liczba M+1
jest pierwsza :)

Gdy posiadamy 'nieco' lepsze narzędzie matematyczne to możemy obliczyc
resztę z dzielenia z jeszcze bardziej nieprawdopobnie wielkiej liczby np

m^m przez 10 061 ( 1234-ta liczba pierwsza)

gdzie m =
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849

i od razu informuję, że ta reszta wynosi 4445

Myśle,że kandydatem do obliczenie tej reszty jesteś ty Maćku ( jezeli
oczywiście posiadasz jakieś zaawansowane narzędzia matematyczne)

[Maciek]

Post by Gik

Post by Maciek

(....................)
tak dla treningu proponuję obliczyć resztę z dzielenia
12345678910^12345678910 przez 47

No, to jeszcze da się zrobić "na piechotę", ręcznie. (...)

'Ręcznie' to może w obecnych czasach już nie, (...)

"W obecnych czasach już nie"? A dlaczegóż to?
Czy współcześnie nie umiemy już pisemnie liczyć?

Z tego co obserwuję na codzień to twoje pokolenie już nie umie

Ciekawe... A które to jest *moje* pokolenie...?


Maciek

[Gik]

Post by Maciek

Post by Gik
Z tego co obserwuję na codzień to twoje pokolenie już nie umie

Ciekawe... A które to jest *moje* pokolenie...?

To ty wiesz najlepiej, które to twoje pokolenie. Dla mnie to ca 15 - 35.
Uważasz, że to młode pokolenie umie liczyc pisemnie ?

[Maciek]

Post by Gik

Post by Maciek

Post by Gik
Z tego co obserwuję na codzień to twoje pokolenie już nie umie

Ciekawe... A które to jest *moje* pokolenie...?

To ty wiesz najlepiej, które to twoje pokolenie.

Co JA wiem, to nie ma tu żadnego znaczenia. Pytam wszak
o to co TY powiedziałeś. Przypisujesz jakieś cechy "mojemu
pokoleniu", więc Ciebie pytam, bo chcę wiedzieć, kogo
właściwie masz na myśli.
Zwłaszcza że skoro piszesz o codziennych obserwacjach,
to chyba wiesz dość dokładnie, kogo obserwujesz.
(Przy okazji: "na co dzień".)

Post by Gik
Dla mnie to ca 15 - 35.

No dobrze - spróbuję zapamiętać, że dla Ciebie
"moim pokoleniem" jest 15 - 35.

Post by Gik
Uważasz, że to młode pokolenie umie liczyc pisemnie ?

A skąd mogę to wiedzieć?! Nie było okazji sprawdzać...

Zresztą, choćbym i dorwał gdzieś na ulicy, w parku
czy pubie kilkanaścioro i przegzaminował, to przecież
nie wystarczyłoby by powiedzieć coś o *pokoleniu*,
prawda? Do tego trzeba by przeprowadzić sprawdzian
na skalę całego kraju...


Maciek

PS
Wiem za to na pewno, że przynajmniej jeden
z przedstawicieli *Twojego* pokolenia miewa
kłopoty z interpunkcją: zdarza mu się wstawić
zbędny odstęp przed znak zapytania, a czasem
gubi kropkę kończącą zdanie. ;)

[Stachu 'Dozzie' K.]

Post by Gik

Post by Maciek
Dziś sprawdziłem wynik arkuszem kalkulacyjnym. Zgadza się.
Czas - ok. 10 minut.

I oto mi chodziło pisząc "ale na pewno wystarczą prymitywne narzędzia
matematyczne np Excel ". Szybko i skutecznie.
Liczba M = 12345678910 ^ 12345678910
posiada 135 802 468 010 cyfr dziesiętnych.

[...]

Post by Gik
Oczywiście liczby M nie mozna zapisać jawnie w żadnym komputerze. Mimmo
to udało się Maćkowi policzyć resztę z dzielenia tej niewyobrażalnie
dużej liczby przez 47 i 173.
No cóż w niektórych dziedzinach matematyki można sięgać bardzo daleko. W
innych niestety nie, np napewno nie uda się stwierdzić, czy liczba M+1
jest pierwsza :)

Bzdura. Istnieje algorytm testowania pierwszości liczby _wielomianowy_
ze względu na długość liczby. Deterministyczny.

Post by Gik
Gdy posiadamy 'nieco' lepsze narzędzie matematyczne to możemy obliczyc
resztę z dzielenia z jeszcze bardziej nieprawdopobnie wielkiej liczby np
m^m przez 10 061 ( 1234-ta liczba pierwsza)
gdzie m =
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849
i od razu informuję, że ta reszta wynosi 4445
Myśle,że kandydatem do obliczenie tej reszty jesteś ty Maćku ( jezeli
oczywiście posiadasz jakieś zaawansowane narzędzia matematyczne)

Znaczy się proste fakty "(a * b) mod n = [(a mod n) * (b mod n)] mod n"
i ograniczoność zbioru reszt z dzielenia przez n są zaawansowanymi
narzędziami?

[Gik]

Post by Stachu 'Dozzie' K.

Post by Gik
Liczba M = 12345678910 ^ 12345678910
posiada 135 802 468 010 cyfr dziesiętnych.

[...]

Post by Gik
No cóż w niektórych dziedzinach matematyki można sięgać bardzo daleko. W
innych niestety nie, np napewno nie uda się stwierdzić, czy liczba M+1
jest pierwsza :)

Bzdura. Istnieje algorytm testowania pierwszości liczby _wielomianowy_
ze względu na długość liczby. Deterministyczny.

Dobre. Liczbę, którą nie można zapisac w żadnym komputerze mozna
testować zapewnie wirtualnie ?.
Mogę zapytac jaką dużą liczbę udało ci się osobiście testowac tą metodą.

Post by Stachu 'Dozzie' K.

Post by Gik
gdzie m =
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849

Znaczy się proste fakty "(a * b) mod n = [(a mod n) * (b mod n)] mod n"
i ograniczoność zbioru reszt z dzielenia przez n są zaawansowanymi
narzędziami?

I to zapewnie można wykonać dla podanego przykładu przy pomocy Excela
lub OO.Calc ?!
Spróbój więc wykonac ty obliczenia OSOBIŚCIE. Sprawdż czy podałem dobry
wynik, lub zmień liczbe 'm' i oblicz swoje dane.

Czekam więc niecierpliwie.

[Maciek]

Post by Gik

Post by Stachu 'Dozzie' K.

[...] No cóż w niektórych dziedzinach matematyki można sięgać
bardzo daleko. W innych niestety nie, np napewno nie uda
się stwierdzić, czy liczba M+1 jest pierwsza :)

Bzdura. Istnieje algorytm testowania pierwszości liczby
_wielomianowy_ ze względu na długość liczby. Deterministyczny.

Dobre. Liczbę, którą nie można zapisac w żadnym komputerze

Tu dopełniacz, nie biernik: *której* nie można zapisać...

Post by Gik
mozna testować zapewnie wirtualnie ?.

A dlaczego by nie?

Nie zaprzeczysz chyba, że choć liczby m^m nie da się zapisać
"wprost", rozwinięciem pozycyjnym, to jednak MOŻNA sprawdzić
jej podzielność na przykład przez 2 lub przez 7?

Post by Gik

Post by Stachu 'Dozzie' K.

gdzie m = 123456789 [ciąg dalszy w następnych wierszach]
1011121314151617181920212223242526272829
3031323334353637383940414243444546474849

Znaczy się proste fakty "(a * b) mod n = [(a mod n) * (b mod n)] mod n"
i ograniczoność zbioru reszt z dzielenia przez n są zaawansowanymi
narzędziami?

I to zapewnie można wykonać dla podanego przykładu
przy pomocy Excela lub OO.Calc ?!

To akurat można choćby tą samą "młotkową" metodą, którą
liczyłem (i potem sprawdzałem arkuszem właśnie) poprzedni
przykład. Tyle że zamiast 34 wierszy potrzeba ze 293 (tyle
cyfr ma rozwinięcie dwójkowe m) i zamiast dwu kolumn - ok.
10 (rozbicie zapisu m na kilkucyfrowe odcinki - "cyfry"
w układzie np. miliardowym).


Maciek

[Gik]

Post by Maciek

Post by Gik

[...] No cóż w niektórych dziedzinach matematyki można sięgać
bardzo daleko. W innych niestety nie, np napewno nie uda
się stwierdzić, czy liczba M+1 jest pierwsza :)

mozna testować zapewnie wirtualnie ?.

A dlaczego by nie?
Nie zaprzeczysz chyba, że choć liczby m^m nie da się zapisać
"wprost", rozwinięciem pozycyjnym, to jednak MOŻNA sprawdzić
jej podzielność na przykład przez 2 lub przez 7?

Przecież pisałem, że 'niektórych dziedzinach matematyki można sięgać
bardzo daleko' . Dotyczy to podzielności.
Napisałem, że nie mozna stwiedzić czy liczba M+1 jest pierwsza. Testować
wirtualnie można podzielnośc ale nie pierszeństwo.

Post by Maciek

Post by Gik

gdzie m = 123456789.........4849

I to zapewnie można wykonać dla podanego przykładu
przy pomocy Excela lub OO.Calc ?!

To akurat można choćby tą samą "młotkową" metodą, którą
liczyłem (i potem sprawdzałem arkuszem właśnie) poprzedni
przykład. Tyle że zamiast 34 wierszy potrzeba ze 293 (tyle
cyfr ma rozwinięcie dwójkowe m) i zamiast dwu kolumn - ok.
10 (rozbicie zapisu m na kilkucyfrowe odcinki - "cyfry"
w układzie np. miliardowym).

Zwiększenie z 34 wierszy do 293 to trywialne i zajmie kilka sekund.
Rozbicie liczby 'm' na kilkucyfrowe odcinki i utworzenie kilku
dodatkowych kolumn jakoś ze sobą powiązane to już nie trywialne. Całośc
trzeba zapewnie wielokrotnie testować. Przypuszczam, że jest to do
zrealizowania choć może ci to zająć równie dużo czasu.
aha ... zostaje jeszcze 'drobny' problem - przeliczenia 'm' na zapis
dwójkowy

[Maciek]

Post by Gik

Post by Maciek

Post by Gik

(...................)
gdzie m = 123456789.........4849

I to zapewnie można wykonać dla podanego przykładu
przy pomocy Excela lub OO.Calc ?!

To akurat można choćby tą samą "młotkową" metodą, którą
liczyłem (i potem sprawdzałem arkuszem właśnie) poprzedni
przykład. Tyle że zamiast 34 wierszy potrzeba ze 293 (tyle
cyfr ma rozwinięcie dwójkowe m) i zamiast dwu kolumn - ok.
10 (rozbicie zapisu m na kilkucyfrowe odcinki - "cyfry"
w układzie np. miliardowym).

Zwiększenie z 34 wierszy do 293 to trywialne i zajmie
kilka sekund. Rozbicie liczby 'm' na kilkucyfrowe
odcinki i utworzenie kilku dodatkowych kolumn jakoś
ze sobą powiązane to już nie trywialne.

Etam. ;) Równie trywialne jak poprzednio rozbicie
zapisu (!) liczby 12345678910 na dwa odcinki.
(Przy okazji: "kilku kolumn" to dopełniacz,
nie mianownik ani biernik, zatem "...powiązanych".)

Post by Gik
(.....) Przypuszczam, że jest to do
zrealizowania choć może ci to zająć równie dużo czasu.

Istotnie równie dużo - kolejne 10 minut. :)

m^m \equiv 6278 (mod 10061)

Post by Gik
aha ... zostaje jeszcze 'drobny' problem - przeliczenia 'm'
na zapis dwójkowy

Jaki problem?... To przecież TEŻ robi arkusz. :D
W każdym z tych 293 wierszy wyznacza kolejną cyfrę
dwójkową wykładnika i wykorzystuje ją do sterowania
obliczeniem kolejnej reszty.



Maciek

[Gik]

Post by Maciek

Post by Gik
(.....) Przypuszczam, że jest to do
zrealizowania choć może ci to zająć równie dużo czasu.

Istotnie równie dużo - kolejne 10 minut. :)
m^m \equiv 6278 (mod 10061)

Brawo! . To jest dobry wynik.
Wynik ten różni się o tego, który wcześniej podałem. Szukając przyczyn
znalazłem, że w swoim programie w ciągu 123..4849 pominąłem '7' i '14'

Post by Maciek

Post by Gik
aha ... zostaje jeszcze 'drobny' problem - przeliczenia 'm'
na zapis dwójkowy

Jaki problem?... To przecież TEŻ robi arkusz. :D
W każdym z tych 293 wierszy wyznacza kolejną cyfrę
dwójkową wykładnika

Nie jest to dla mnie jasne.
W normalnym algorytmie kolejną cyfrę dwójkową wykładnika oblicza się
przez cykl dzielenia całkowitego przez 2 i modulo 2.
Jak w arkuszu można wykonać dzielenie 123...4849 przez 2 .
Jaki konkretnie arkusz kalkulacyjny używałeś ?

[Maciek]

Post by Maciek

(......................)
(...) jeszcze 'drobny' problem - przeliczenia 'm'
na zapis dwójkowy

Jaki problem?... To przecież TEŻ robi arkusz. :D
W każdym z tych 293 wierszy wyznacza kolejną cyfrę
dwójkową wykładnika

Nie jest to dla mnie jasne. (.........)
Jak w arkuszu można wykonać dzielenie 123...4849 przez 2 .

Dokładnie tak samo, jak "na piechotę" - pisemnie. :-)

Nie zostawiaj odstępu przed kropką.

Jaki konkretnie arkusz kalkulacyjny używałeś ?

*Jakiego arkusza* używałem (używa się *czego*, nie *co*
- jedynym wyjątkiem jest seria debilnych reklam Calgonu).
Nie zostawiaj odstępu przed pytajnikiem.


Nie napiszę jakiego, bo i tak go prawie na pewno
nie znasz (prawie... na jakieś 99,95%). Zresztą
nieistotne, rachunek wygląda tak samo w każdym.

Weźmy na przykład liczbę 1234567890 w rozbiciu
na trzy kolumny. To daje 4-cyfrowe odcinki zapisu.
Piszemy w pierwszym wierszu:

A1: 12
A2: 3456
A3: 7890

- jest to oczywiście TRZYCYFROWY zapis tej samej liczby
w układzie o podstawie dziesięć tysięcy (a każda cyfra
zapisana dziesiętnie).

W kolejnych wierszach dzielimy ją - "pisemnie" - przez 2,
dzieląc każdą "cyfrę" i dobierając w razie potrzeby
przeniesienie z poprzedniej "cyfry":

B1: int( A1 / 2 )
B2: int( (mod(A1, 2) * 10000 + A2) / 2 )
B3: int( (mod(A2, 2) * 10000 + A3) / 2 )

C1: int( B1 / 2 )
C2: int( (mod(B1, 2) * 10000 + B2) / 2 )
C3: int( (mod(B2, 2) * 10000 + B3) / 2 )

....

Cyfry rozwinięcia dwójkowego - o ile potrzebujemy je
sobie wyświetlić - obliczamy w dodatkowej kolumnie:

A4: mod(A3, 2)
B4: mod(B3, 2)
C4: mod(C3, 2)
.....

Ot i cały "problem".

Rozszerzenie na większe liczby jest oczywiste: sprowadza
się do powielenia odpowiednią liczbę razy schematu
z kolumny 2 i 3, oraz, oczywiście, zwiększenia "podstawy"
zapisu, czyli liczby cyfr, wykorzystanych w poszczególnych
kolumnach. Powyżej użyłem odcinków tylko 4-cyfrowych aby
rozwiązanie było bardziej czytelnie. W praktyce można
dziś liczyć, że arkusz spamięta bez zaokrągleń liczby
rzędu nawet 1e14 (piętnaście cyfr precyzji daje 64-bitowy
zapis zmiennoprzecinkowy 'double precision' wg standardu
IEEE 754). Jednakże do działań typu "reszta z dzielenia"
arkusz mógłby przekształcać liczby na zapis całkowitoliczbowy
- i jeśli nie korzysta z formatu 80- lub choćby 64-bitowego,
to na poprawne wyniki można liczyć tylko pod warunkiem
utrzymania się w granicach 1e9.


Oczywiście int() i mod() symbolizują obliczenie części
całkowitej oraz reszty z dzielenia. Wdrażając przedstawiony
schemat trzeba je zastąpić funkcjami lub operatorami
istniejącymi w użytym arkuszu.


Maciek

[Stachu 'Dozzie' K.]

Post by Maciek
Wczoraj przez chwilę (hm, powiedzmy ;)) nie miałem
ciekawszych zajęć (hm, powiedzmy ;)) i porachowałem.
12345678910 ^ 12345678910 = 14 (mod 47)
12345678910 ^ 12345678910 = 150 (mod 173)
Narzędzia: kartka, pisak i czterodziałaniowy kalkulator.
Zajęło jakieś 3 godziny (pisemne przeliczenie wykładnika

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Post by Maciek
na zapis dwójkowy, z dwiema pomyłkami - około pół godziny;

^^^^^^^^^^^^^^^^^

Post by Maciek
dzielenie pisemne podstawy przez 47 i 173 w celu znalezienia
reszt, w tym trzy pomyłki - około kwadransa; wyznaczenie
pierwszej reszty z potęgi - około godziny; wyznaczenie
drugiej reszty, z jedną pomyłką - niecałe półtorej h).

Ę? Metoda mastodonta nie popłaca. Przecież zbiór reszt z dzielenia przez
n jest skończony. Rząd elementu k modulo n (działaniem jest mnożenie)
jest jeszcze mniejszy. Naprawdę nie wiem, po co liczyłeś tak wysoką
potęgę.

[Gik]

Post by Stachu 'Dozzie' K.

Post by Maciek
Zajęło jakieś 3 godziny (pisemne przeliczenie wykładnika

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Post by Maciek
na zapis dwójkowy, z dwiema pomyłkami - około pół godziny;

^^^^^^^^^^^^^^^^^
Ę? Metoda mastodonta nie popłaca. Przecież zbiór reszt z dzielenia przez
n jest skończony. Rząd elementu k modulo n (działaniem jest mnożenie)
jest jeszcze mniejszy. Naprawdę nie wiem, po co liczyłeś tak wysoką
potęgę.

Myśle, ze najpierw powinieś chwilkę pomyśleć o czym pisze przedmówca.

Metoda zastosowana przez Maćka jest trudniejsza, ale w wielu przypadkach
znacznie szybciej prowadzi do celu.
W konkretnym przypadku zbiór reszt dzielenia przez 47 i 173 wynosi
odpowiednio 46 i 172. A Maciek potrzebował tylko 34 kroki do osiągniecia
celu.

[Stachu 'Dozzie' K.]

Post by Gik

Post by Stachu 'Dozzie' K.

Post by Maciek
Zajęło jakieś 3 godziny (pisemne przeliczenie wykładnika

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Post by Maciek
na zapis dwójkowy, z dwiema pomyłkami - około pół godziny;

^^^^^^^^^^^^^^^^^
Ę? Metoda mastodonta nie popłaca. Przecież zbiór reszt z dzielenia przez
n jest skończony. Rząd elementu k modulo n (działaniem jest mnożenie)
jest jeszcze mniejszy. Naprawdę nie wiem, po co liczyłeś tak wysoką
potęgę.

Myśle, ze najpierw powinieś chwilkę pomyśleć o czym pisze przedmówca.

Pisze o podnoszeniu liczby do astronomicznych potęg. Ja z kolei sądzę,
że ty powinieneś chwilkę pomyśleć nad tym, co powiedziałem _ja_.
I odnoszę wrażenie, że douczyć się algebry i teorii liczb.

Post by Gik
Metoda zastosowana przez Maćka jest trudniejsza, ale w wielu przypadkach
znacznie szybciej prowadzi do celu.
W konkretnym przypadku zbiór reszt dzielenia przez 47 i 173 wynosi
odpowiednio 46 i 172. A Maciek potrzebował tylko 34 kroki do osiągniecia

A, niech będzie że policzę. 47 i 173 to liczby pierwsze, więc można
mówić o grupach z mnożeniem modulo (uprości to terminologię).
W przypadku grupy modulo 47, 1234567890 ma rząd 24, więc wymagałoby
mniej operacji niż Maciek wykonał. W przypadku grupy modulo 173
1234567890 niestety już jest generatorem.

Jednak zauważywszy, że 47 i 173 _mogą być_ liczbami pierwszymi można
było sprawdzić, czy 1234567890 ^ (n - 1) = 1 (mod n).
Naturalnie n nie musi być liczbą pierwszą, żeby tak było. To w niczym
nie przeszkadza, bo w tym momencie mamy już okres w ciągu kolejnych
potęg.

[Gik]

Post by Stachu 'Dozzie' K.

Post by Gik
Myśle, ze najpierw powinieś chwilkę pomyśleć o czym pisze przedmówca.

Pisze o podnoszeniu liczby do astronomicznych potęg.

O to nieprawda. Podnosi tylko do kwadratu i to moduł - 34 razy

Post by Stachu 'Dozzie' K.
Ja z kolei sądzę,
że ty powinieneś chwilkę pomyśleć nad tym, co powiedziałem _ja_.
I odnoszę wrażenie, że douczyć się algebry i teorii liczb.

Myślę, że terminy ' douczyć się ', 'bzdura' nie są argumentami
matematycznymi.

Post by Stachu 'Dozzie' K.
A, niech będzie że policzę. 47 i 173 to liczby pierwsze, więc można
mówić o grupach z mnożeniem modulo (uprości to terminologię).
W przypadku grupy modulo 47, 1234567890 ma rząd 24, więc wymagałoby
mniej operacji niż Maciek wykonał. W przypadku grupy modulo 173
1234567890 niestety już jest generatorem.

Metoda stosowana przez Maćka( rozłożenia wykładnika binarnie) wymaga
zawsze tej samej liczby kroków ( w tym przypadku 34). W przypadku
korzystania z okresowosci zbioru reszt liczba operacji zależy od
dzielnika. W przypadku 47 jest to korzystne ale w przypadku 173 niestety
nie. Im większy dzielnik tym mniejsze szanse na to, że metoda ta będzie
szybsza.

Post by Stachu 'Dozzie' K.
Jednak zauważywszy, że 47 i 173 _mogą być_ liczbami pierwszymi można
było sprawdzić, czy 1234567890 ^ (n - 1) = 1 (mod n).

47 i 173 są liczbami pierwszymi ( _mogą być_ ?)
Nie wiem poco to mam sprawdzić ( tzn raczej sie domyślam) ale pytanie
brzmi jak ja to mam zrobić prosto, szybko i skutecznie.

Post by Stachu 'Dozzie' K.
Naturalnie n nie musi być liczbą pierwszą, żeby tak było. To w niczym
nie przeszkadza, bo w tym momencie mamy już okres w ciągu kolejnych
potęg.

Próbowałem skorzystać z twojej rady 'pomyśleć nad tym, co powiedziałem
_ja_. -> tzn ty). Niestety skróty myślowe są tak duże, że nie
zrozumiałem co myślałeś.

Pamiętaj, że każda grupę czytają też ludzie, którzy wprawdzie nie piszą
ale ją czytają, żeby coś nowego się dowiedzieć.
Załóż nowy watek i opisz dokładnie preferowaną metodę tak by było to
zrozumiałe dla wszystkich. Będzie to napewno pożyteczne dla ogółu
czytelników.

[Stachu 'Dozzie' K.]

Post by Stachu 'Dozzie' K.

Post by Gik
Myśle, ze najpierw powinieś chwilkę pomyśleć o czym pisze przedmówca.

Pisze o podnoszeniu liczby do astronomicznych potęg.

O to nieprawda. [...]

Według ciebie 1234567890 to mała potęga?

Post by Stachu 'Dozzie' K.
Ja z kolei sądzę,
że ty powinieneś chwilkę pomyśleć nad tym, co powiedziałem _ja_.
I odnoszę wrażenie, że douczyć się algebry i teorii liczb.

Myślę, że terminy ' douczyć się ', 'bzdura' nie są argumentami
matematycznymi.

O, to i z rozumieniem języka polskiego miewasz problem?

Post by Stachu 'Dozzie' K.
A, niech będzie że policzę. 47 i 173 to liczby pierwsze, więc można
mówić o grupach z mnożeniem modulo (uprości to terminologię).
W przypadku grupy modulo 47, 1234567890 ma rząd 24, więc wymagałoby
mniej operacji niż Maciek wykonał. W przypadku grupy modulo 173
1234567890 niestety już jest generatorem.

Metoda stosowana przez Maćka( rozłożenia wykładnika binarnie) wymaga
zawsze tej samej liczby kroków ( w tym przypadku 34). W przypadku
korzystania z okresowosci zbioru reszt liczba operacji zależy od
dzielnika. W przypadku 47 jest to korzystne ale w przypadku 173 niestety
nie. Im większy dzielnik tym mniejsze szanse na to, że metoda ta będzie
szybsza.

Post by Stachu 'Dozzie' K.
Jednak zauważywszy, że 47 i 173 _mogą być_ liczbami pierwszymi można
było sprawdzić, czy 1234567890 ^ (n - 1) = 1 (mod n).

47 i 173 są liczbami pierwszymi ( _mogą być_ ?)

Na pierwszy rzut oka.

Nie wiem poco to mam sprawdzić ( tzn raczej sie domyślam) ale pytanie

^^^^-- co to za słowo?

brzmi jak ja to mam zrobić prosto, szybko i skutecznie.

Jest prosto, szybko i skutecznie.

Post by Stachu 'Dozzie' K.
Naturalnie n nie musi być liczbą pierwszą, żeby tak było. To w niczym
nie przeszkadza, bo w tym momencie mamy już okres w ciągu kolejnych
potęg.

Próbowałem skorzystać z twojej rady 'pomyśleć nad tym, co powiedziałem
_ja_. -> tzn ty). Niestety skróty myślowe są tak duże, że nie
zrozumiałem co myślałeś.

Mówisz o powszechnie w algebrze używanych skrótach myślowych?

Albo postawmy sprawę inaczej. Którego słowa w moim opisie nie
zrozumiałeś?

[gronki]

Dnia 28-06-2006 o 13:14:17 Nothingman

Post by Nothingman
1111^4444 przez 21...

Nie wiem, czy takie rozwiązanie się przewinęło, ale może będzie - może o
tyle nie bardziej pięknie nieskomplikowane - ale na prostszych podstawach..
1111 mod 21 = 19 (co się jeszcze mieści w ramach "ludzkich" obliczeń, a
jest już zupełnie trywialne jeśli dozwolone są kalkulatory),
więc można powiedzieć, że
1111^4444 = (21n - 2)^4444
Po rozwinięciu tego wielomianu (W(n)) wszystkie jego wyrazy oprócz wolnego
będą podzielne przez 21. Wyraz wolny wynosi 2^4444, a reszty z dzielenia
kolejnych potęg dwójek (nie zastanawiałem się nigdy nad dowodem,
zauważyłem to przy okazji, ale nie tylko dwójek, powiedzmy, że dowodem
będzie to, że któryś z sz.kolegów już to wymienił ;-) ) przez 21
powtarzają się w 6-elementowym cyklu, co też można stwierdzić bez
wyszukanych sposobów. 4444 nie jest podzielne przez 6, ale 4440 już jest.
Reszta z dzielenia 2^4440 mod 21 = 1, a więc skoro 2^4444 = 2^4440*2^4 to
2^4444 mod 21 = 2^4 = 16. Ponieważ wyraz wolny ma znak dodatni, to 16 jest
resztą z całego dzielenia.
Proszę o pozytywne nastawienie do mojej wypowiedzi (również dlatego, że
jestem tu nowy), ale gdyby kogoś uderzyło coś negatywnego w tym poście, to
proszę wybaczyć, jestem słabo wyedukowanym samoukiem.
Pozdrawiam :)
g.