Strona używa cookies (ciasteczek). Dowiedz się więcej o celu ich używania i zmianach ustawień. Korzystając ze strony wyrażasz zgodę na używanie cookies, zgodnie z aktualnymi ustawieniami przeglądarki.    X

Mój patent na błyskawiczne szacowanie dowolnie dużych potęg dwójki

W zależności od tego, jakim działem informatyki się interesujecie, z liczbami binarnymi będziecie obcować rzadziej lub częściej. Tak czy inaczej, wiedza na temat tego, ile w przybliżeniu wynosi 2^N dla zadanej zmiennej N czasem się przydaje, czy to w pracy na co dzień, czy to przy okazji zapoznawania się ze specyfikacją jakiejś technologii. Całkiem możliwe, że wiedza ta przyda Wam się również na kolokwium z teoretycznych podstaw informatyki, algorytmów i struktur danych, czy też podstaw bezpieczeństwa komputerowego.

We wpisie tym chce pokazać, że jeśli kiedykolwiek przyjdzie Wam oszacować 'mniej więcej' (dla lepszej i szybkiej orientacji), jaką wartość niesie ze sobą wynik takiego potęgowania, to dokonywanie jakichkolwiek większych obliczeń wcale nie jest wymagane, co wynika z samej natury liczb binarnych i ich częściowej powtarzalności. Wystarczy jedynie zapamiętać kilka (co najmniej dwie, w optymalnym wypadku trzy lub więcej) potęg dwójki (najlepiej 0, 1, 5, 10), by móc sprawnie szacować wyniki dowolnie dużych operacji potęgowania liczby 2. Rozważmy następujące problemy:

  • Ile komputerów można zaadresować w ramach IPv4 przeznaczając na hosty 12 bitów?
  • Ile operacji wykona algorytm o wykładniczej złożoności obliczeniowej O(2^n) dla danych o rozmiarze 16?
  • Ile kolorów można wyświetlić po ustawieniu w systemie głębi kolorów na TrueColor (24 bity)?
  • Ile maksymalnie pamięci jest w stanie zaadresować 32-bitowy system operacyjny?
  • Jaką maksymalną liczbę całkowitą można przechować w pamięci w ramach 64-bitowego typu całkowitego bez znaku?

Wszystkie te pytania sprowadzają się do prostego wykonania operacji potęgowania, w której podstawą jest liczba 2, zaś wykładnikiem liczba wspomnianych w danym problemie bitów.

Jeśli zachodzi potrzeba odpowiedzieć na nie w sposób jak najbardziej precyzyjny, wówczas nie pozostaje Wam dziś nic innego, jak tylko sięgnąć po kalkulator. Zadajmy sobie jednak następujące pytanie, a mianowicie, jak często rozwiązując powyższe problemy potrzebujemy dokładnego wyniku? Bo jeśli interesuje nas tylko i wyłącznie wynik przybliżony, to okazuje się, że po krótkim ćwiczeniu zamiast te potęgi liczyć (czy to w pamięci, czy na kalkulatorze), będziecie mogli po prostu je 'odczytywać'.

Wróćmy jeszcze do powyższych przykładowych pytań. Jestem przekonany, że gdy administrator systemu lub sieci wylicza liczbę adresów do wykorzystania z dostępnych 12 bitów, to dzięki swojemu doświadczeniu nie musi wiedzieć precyzyjnie, że może z nich uzyskać 4096 - 2 hosty, lecz wystarczy mu wiedzieć, że będzie to 4 tysiące hostów. Gdy pytamy o liczbę operacji algorytmu wykładniczego dla danych o rozmiarze 16, to na ogół wystarczy wiedzieć, że będzie to około 64 tysiące operacji, a nie dokładnie 65536. Jeśli użytkownik spyta nas, ile kolorów zyska po aktywacji na swoim komputerze 24-bitowego trybu TrueColor, wówczas wystarczy odpowiedzieć mu, że będzie to ponad 16 mln kolorów (a nie 16777216). Dodatkowo poinformujemy go, że jego 32-bitowy system nie jest w stanie zaadresować więcej jak 4 GB RAM-u, nie skupiając się dokładnie na liczbie 4294967296 bajtów pamięci.

Jeśli zależy Wam tylko i wyłącznie na takim właśnie przybliżeniu, to nie musicie w zasadzie niczego liczyć, bo wszystkie potrzebne informacje zawierają się już w samej liczbie bitów. Wystarczy tylko znać lub szybko zapamiętać sobie podstawowe potęgi, takie jak 2 do 0, 2 do 1, 2 do 5 i 2 do 10. Wy już je znacie na pamięć, prawda? Moja metoda 'odczytywania' wartości dowolnej potęgi dwójki przedstawia się następująco (jeśli mój opis nie jest dla Was zbyt klarowny, to możecie spróbować od razu przejść do poniższych przykładów):

Wzór ogólny do rozwiązania tego rodzaju problemów: 2^N

Jako że interesuje nas jedynie wykładnik, to możemy skupić się tu tylko na nim. Mamy więc pewną liczbę bitów (wykładnik), w ogólnym przypadku N.

Odczytujemy pierwszą cyfrę z prawej w wykładniku potęgi. Cyfra ta staje się liczbą, do której faktycznie potęgujemy dwójkę. Biorąc pod uwagę, że może w tym miejscu stać wyłącznie pojedyncza cyfra od 0 do 9, bardzo łatwo będzie nam uzyskać wynik. Jako że większość z Was zapewne doskonale zna wyniki potęgowania dwójki dla wykładników 0, 1, 5 i 10, na ich podstawie będziecie mogli szybko obliczyć pozostałe potęgi, odpowiednio mnożąc lub dzieląc znaną Wam już liczbę przez dwa. Jeśli znacie wszystkie potęgi dwójki od 0 do 10, to nie musicie się już niczego uczyć do sprawnego szacowania większych potęg.

Wróćmy jednak do sedna sprawy. Zapisujemy ten 'zredukowany' wynik potęgowania dwójki z wykładnikiem będącym cyfrą najbardziej na prawo. Następnie z pierwotnego wykładnika (czy jak kto woli, samej liczby bitów N) odczytujemy liczbę utworzoną z pozostałych cyfr, ale czytaną tym razem od lewej. Uzyskana teraz liczba to nic innego jak rząd wielkości naszego wyniku, lub z perspektywy zapisu liczba grup trójek zer. Spójrzmy na przykład:

Ile hostów można zaadresować przy wykorzystaniu 12 bitów?

Szacujemy tu, ile to jest 2^12 (możemy skupić się po prostu na samych bitach, czyli liczbie 12)

Cyfra najbardziej na prawo w wykładniku 12 to 2, więc dwójkę podnosimy właśnie do tej liczby (cyfry). Operacja jest teraz bardzo prosta, 2^2 = 4. Liczba 4 wędruje na przód naszego końcowego wyniku, który sobie pewnie gdzieś notujemy, najlepiej w pamięci.

Pozostałe cyfry, tym razem czytane od lewej, symbolizują rząd wielkości naszego wyniku. W naszym przykładzie mamy cyfrę 1, czyli po prostu jedną grupę trójek zer (000), którą dopisujemy na koniec.

W ten sposób otrzymujemy dwie rzeczy: liczbę 4 oraz jedną grupę zer 000. Daje nam to oszacowanie wynoszące w przybliżeniu 4 000, czyli 4 tysiące.

Odpowiedź: Przy wykorzystaniu 12 bitów z części hosta adresu IPv4 można zaadresować około 4 tysiące komputerów.

Kolejny przykład wykonamy już nieco szybciej.

Ile operacji wykona algorytm o wykładniczej złożoności obliczeniowej O(2^n) dla danych o rozmiarze 16?

Cyfra od prawej to 6, więc 2^6 to (już z pamięci) 64. Zapisujemy 64.
Pozostałe cyfry (czytane od lewej) to 1, więc tylko jedna grupa zer (lub rząd wielkości równy tysiąc). Dopisujemy 000 i otrzymujemy oszacowanie równe 64 tysiące (podczas gdy dokładny wynik to 65536).

Teraz będzie jeszcze szybciej.

Ile kolorów można wyświetlić po ustawieniu głębi kolorów na 24 bity (TrueColor)?

2^4 to 16, zaś czytane od lewej cyfry to 2, a zatem dwie grupy zer (rząd wielkości to milion). Nasze oszacowanie to 16 000 000, czyli 16 milionów kolorów.

Ile maksymalnie pamięci jest w stanie zaadresować system 32-bitowy?

2^2 to 4, mamy trzy grupy zer, więc tym razem miliard. Oszacowana odpowiedź to 4 miliardy bajtów, a więc 4 GB pamięci RAM.

Jaką maksymalną liczbę całkowitą można wyrazić przy użyciu 64-bitowego typu całkowitego integer bez znaku?

2^4 to 16 i mamy aż sześć grup zer, więc będziemy operować na trylionach (poprawcie mnie, jeśli źle nazwałem). Teraz już wiemy, że 64-bitowy unsigned integer może przechować liczby do około 16 trylionów (w angielskim to już kwintyliony).

Jak widać, tym sposobem można szybko oszacować dowolną potęgę dwójki, przy czym im większa potęga, tym większa rozbieżność pomiędzy naszym oszacowaniem a dokładnie obliczonym wynikiem potęgowania. Na ogół takie oszacowanie jest w pełni wystarczające i pozwala nam się dokładnie zorientować, jak duża jest dana liczba. Ewentualnie zawsze przy podawaniu oszacowania możemy sobie (lub komuś) dodać słówko 'mniej więcej' lub 'ponad'. Na pewno nie jeden Wasz przyjaciel będzie zdziwiony, gdy w ciągu dwóch-trzech sekund będziecie potrafili powiedzieć, ile to mniej więcej jest 2^38. Wystarczy spojrzeć na 8-kę, i zanim wypowiecie 256 będziecie wiedzieli, że trzeba dodać trzy grupy zer, a więc będzie to 'nieco ponad' 256 mld (w rzeczywistości to dokładnie 274 mld z groszem).

Na koniec jeszcze trzy przykłady dla pewności i już możecie szacować duże potęgi dwójki właściwie samym wzrokiem.

Ile to jest 2^49?

Cyfra na prawo to 9, więc interesuje nas 2^9. Jeśli nie pamiętacie, ile to jest, możecie dojść do tej liczby ręcznie - wiecie zapewne, że 2^10 to 1024, więc 2^9 to liczba o połowę mniejsza, a więc 512. Jeśli pamiętacie przykładowo, że 2^5 to 32, to idąc tym samym tropem możecie dojść do potęgi 9 ręcznie. Skoro 2^5 to 32, to 2^6 to 64, 2^7 to 128, 2^8 to 256, a tym samym 2^9 to 512. Zacznijmy więc jeszcze raz, by zrobić to szybko.

2^9 to 512. Teraz czytamy pozostałe cyfry od lewej. W tym wypadku będzie to 4, czyli 4 grupy zer (rząd wielkości to bilion). Mamy więc 512 i 000 000 000 000, czyli razem 512 000 000 000 000, a więc 512 bilionów.

Ile to jest 2^71?

2^1 to 2 i mamy 7 grup zer, a więc nasze oszacowanie to 2 000 000 000 000 000 000 000. Tu rozbieżność będzie już spora, ale zawsze mamy ogólny pogląd na 'rozmach' takiej liczby.

Ile to jest 2^128?

Na koniec bardziej interesujący przykład - teoretyczna liczba dostępnych adresów IPv6 (adresy są 128-bitowe):

2^128

Najpierw cyfra z prawej: 2^8 to 256.
Teraz liczba grup, których w tym wypadku jest aż 12. Tym samym nasze oszacowanie to 256 000 000 000 000 000 000 000 000 000 000 000 000. Mniej więcej tyle adresów można uzyskać w przypadku IPv6. Nam wyszło 256, a dokładnie jest to już 340... czegoś. Nawet nie będę tej liczby nazywał. Wolfram Alpha podpowiada, że jest to dokładnie 340 undecylionów, a po naszemu to 340 miliardów miliardów miliardów miliardów.

W tym przypadku rozrzut pomiędzy oszacowaniem a rzeczywistą liczbą jest już gigantyczny, dlatego też proponuję stosować wspomniane magiczne słówko 'ponad'.

Czy ta porada była dla Was przydatna? 

porady

Komentarze

0 nowych
#r2d2#   10 #1 24.01.2016 15:47

Łał, ale super! Wielkie dzięki za ten poradnik. :-)

  #2 24.01.2016 15:52

Wpis miesiąca :)

Farkas   10 #3 24.01.2016 16:58

Będziesz sławny :) :D

psejta3   4 #4 24.01.2016 17:06

Mega proste :) Przyda się na zawodowych :D

Jaro070   15 #5 24.01.2016 17:12

A masz sposób na szybkie szacowanie potęg innych liczb?

dragon321   9 #6 24.01.2016 18:30

Dobry sposób, nie ma co :)

Przyda się do szybkiego szacowania przybliżonej wartości takich dużych potęg.

vbruder   6 #7 24.01.2016 20:30

@Jaro070: Nie, po prostu kiedyś rozpisałem sobie te wszystkie potęgi na kartce i zwróciłem uwagę, że cyfry z przodu zawsze się powtarzają, bez względu na rozmiar wykładnika. Oczywiście im dalej, tym przybliżenie będzie gorsze, ale chyba nikt nas nie będzie męczył potęgami większymi niż 128 od IPv6.

En_der   9 #8 24.01.2016 21:32

Porada jak najbardziej przydatna, a nawet w moim przypadku wzbudziła nowe pożądanie, czyli chciałbym mieć na swoim bankowym koncie, te 340 undecylionów ;)

sagraelski   6 #9 25.01.2016 08:23

Sprytne i przydatne! :)

  #10 25.01.2016 10:03

Gratuluję! Zawsze lepiej dojść samemu do sensownego rozwiązania, Satysfakcja gwarantowana. Nawet kiedy już inni to wymyślili wcześniej i można o tym przeczytać :)

Mój kolega kiedyś wymyślił sito Arystotelesa na potrzeby algorytmu szukania liczb pierwszych. Łebski z niego chłop był.

Dowodzi to, że inteligencja ludzka i kreatywność szybciej dochodzi nawet do zaawansowanych rozwiązań od zera niż ucząc się spisanych już w książkach czy internetach. Czasowo szybciej coś wymyślić niż szukać jak to rozwiązali inni.
Wybiegając w przyszłość - AI nie będzie zbytnio potrzebowała naszej, spisanej przez wieki wiedzy. Będzie tak potężna, że problemy będzie kreatywnie rozwiązywać na bieżąco, całkiem możliwe, że z lepszym efektem.

kowgli   6 #11 25.01.2016 10:28

Korzystasz z zależności że:
2^10 ~= 1000 - tysiąc (kilo)
2^20 ~= 1000000 - milion (mega)
2^30 ~= 1000000000 - miliard (giga)
2^40 ~= 1000000000000 - bilion (tera)
itd.

Autor edytował komentarz.
vbruder   6 #12 25.01.2016 11:03

@kowgli: A i owszem :)

kowgli   6 #13 25.01.2016 11:14

@vbruder:
No to warto by to podkreślić, bo cały twój sposób się do tego sprowadza, że 2^10 ~= 1000 :)

Autor edytował komentarz.
vbruder   6 #14 25.01.2016 12:17

@kowgli: W zasadzie jest to oczywiste, ale nawet jeśli by wtłuc komuś do głowy, że 2^10 to ~tysiąc, a 2^20 to ~milion, itd., to nadal będzie to dla większości zbyt sucha informacja do zapamiętania i wychwycenia wzorca. Chciałem o tym wspomnieć w tekście, ale od jeszcze innej strony, niż Ty to zrobiłeś.

Najciekawsze jest chyba to, że ten wpis miał powstać na DP już kilka lat temu (zaraz po uruchomieniu tutejszej usługi blogowania). Nawet zacząłem go pisać, ale pomyślałem sobie, że nie jest na tyle istotny, by go publikować. Teraz jednak uświadomiłem sobie, jak wiele osób ma problem z oszacowaniem takiej liczby.

  #15 25.01.2016 14:10

@Jaro070: Ja znam sposób na szybkie szacowanie wartości 10^n ;-)

clubber84   4 #16 26.01.2016 20:14

Masz ode mnie głos na wpis miesiąca za pomysł na bardzo szybkie szacowanie przybliżonej wartości potęgi dwójki.
Tęgie głowy pewnie by tego nie wymyśliły. :-)

Pozdrawiam

vbruder   6 #17 26.01.2016 21:33

@clubber84: Dzięki, ale do wpisu miesiąca to chyba jeszcze sporo brakuje. Tak czy inaczej widzę, że się kilku osobom przydało :)

Amaterasu   9 #18 29.01.2016 12:28

Superowa metoda, na stówkę mi się przyda w przyszłości :). Nie musi być ona daleka, może być też i bliska.

Autor edytował komentarz.
allertec   7 #19 01.02.2016 21:37

Na bank się przyda... dzięki...