Implication as an Operator

A vast majority of code is dealing with logical conditions by using three dedicated operators: not (negation), and (conjunction), or (alternative). These are often written as !, && and ||, respectively, in C-like programming languages.

In principle, this is sufficient. Coupled with true and false, it’s enough to encode any boolean function of zero, one or two arguments. But language designers didn’t seem to be concerned with minimalism here, because it’s possible to replace those three operators with just one of the following binary functions:

If you can’t immediately see how, start with deriving negation first.
So we already have some redundancy for the sake of readability. While it’s surely a bad idea to try and incorporate all 22 before mentioned functions, isn’t there at least few others that would make sense as operators on their own?

I can probably think of one: the material implication (). It may seem like a weird choice at first, but there are certain common scenarios where such operator would make things more explicit.
Imagine for a second that some mainstream language (like Java) has been enhanced with operator => that acts as implication. Here’s one example of its straightforward usage:

Many situations involving “optionals” could take advantage of logical implication as an operator. Also note how in this case, the alternatives do not look very appealing at all. One could use an if statement to produce equivalent construct:

but this makes a trivial one-liner suddenly look quite involved. We could also expand the implication using the equivalence law :

Reader would then have to perform the opposite transformation anyway, in order to restore the real meaning hidden behind the non-obvious ! and || operators. Finally, we could be a little more creative:

and capture the intent almost perfectly… At least until along comes someone clever and “simplifies” the expression into the not-a-or-b form presented above.

Does any language actually have the implication operator? Not surprisingly, the answer is yes – but it’s most likely a language you wouldn’t want to code in. Older and scripting versions of Visual Basic had the Imp operator, intended to evaluate the logical connective .
Besides provoking a few chuckles with its hilarious name, its usefulness was limited by the fact that it wasn’t short-circuiting. Both arguments were always evaluated, even if the first one turned out false. You may notice that in our NameMatcher example, such a behavior would produce NullPointerException when one of the names is null. This is also the reason why implication implemented as a function:

would not work in most languages, for the arguments are all evaluated before executing function’s code.

Self-Reinforcement and Exponential Functions

Special relativity is really kind of mean. Not only it prohibits anything from going faster than the speed of light (therefore destroying our Star Trek-inspired dreams of interstellar travel) but also threatens with extreme adverse effects should anyone dare to even come close to the impenetrable barrier of c. Assuming we can deal with the steady increase of mass as the speed goes up, there is always this issue of time dilation. While you are taking your short (i.e. few years-long) trip to nearby star, time passed on Earth could very well be measured in centuries. Having a millennium to catch up might prove cumbersome, and rather frustrating. Just think of all the iPhone models you would have missed!

As a solace, though, you could get quite a pile of cash waiting for you to pick up. Let’s say you’ve put 10,000 dollars (or euro, or your favorite currency) into investment with a yearly interest rate of 10 percent. Every year, this deposit will therefore increase by one tenth, and this will happen continuously over the next 1000 years. Could you quickly tell how big the final amount will be, compared to the initial one? How many times will it increase?…

You shouldn’t be very hard on yourself if you answered instinctively with e.g. 100 times or something similar. I mean, such figures are totally, utterly wrong by many orders of magnitude because the actual value is bigger than 10⁴⁰. But it’s absolutely common to have problems with grasping exponential functions intuitively. In many ways this is quite pitiful, for they accurately describe many phenomenons that occur in nature, civilization, technology and culture. Yet they often escape understanding, leading to unfulfilled predictions, incorrect extrapolations, and plain old cognitive biases.

What is so bizarre about these functions that they tend to confuse a significant fraction, if not the majority of people?…

Eksperyment z losowymi ciągami

Zdarzyło się dzisiaj, że musiałem zaimplementować rozwiązanie wyjątkowo klasycznego problemu. Siląc się matematyczny formalizm, mógłbym go zdefiniować następująco:

• Mamy dany zbiór dowolnych elementów oraz liczbę naturalną .
• Szukamy ciągu k elementów .

Krótko mówiąc, chodzi o trywialną wariację z powtórzeniami. Ambitne to zadanie jest w sumie nawet mniej skomplikowane niż częste ćwiczenie dla początkujących pt. losowanie Lotto, więc po chwili wyprodukowałem coś podobnego do kodu poniżej:

I na tym pewnie historia by się zakończyła, gdybym nie przypomniał sobie, że Python domyślnie potrafi obsługiwać naprawdę duże liczby. (Może nie aż tak duże jak te tutaj, ale jednak dość spore ;]). Obserwacja ta daje się bowiem połączyć z inną: taką, iż ciąg elementów z pewnego zbioru jest równoważny liczbie w systemie o podstawie równej mocy tego zbioru. Taka liczba jest oczywiście bardzo duża w prawie każdym praktycznym przypadku, lecz to nie umniejsza w niczym prawdziwości stwierdzenia. Jest ono zresztą z powodzeniem wykorzystywane w systemach kryptograficznych w rodzaju RSA.

Postanowiłem więc i ja z niego skorzystać. Przynajmniej teoretycznie fakt ten powinien dawać lepsze rezultaty, zamieniając k losowań na tylko jedno – tak jak poniżej:

Doświadczenie z kolei uczyłoby, że bezpośrednie aplikowanie dziwnych matematycznych koncepcji do programowania rzadko miewa dobre skutki ;) Jak więc jest w tym przypadku?…

W obronie π

Doprawdy ciekawe pomysły można czasami znaleźć w Internecie. Na pierwszy rzut mogą wydawać się zupełnie szalone, lecz po bliższym przyjrzeniu daje się w nich zauważyć pewien sens… Ale zwykle tylko pewien, tj. niewielki :) Tak właśnie jest z ideą “nowej stałej okręgu” – liczbą (równą ), której to propozycja zawarta jest tekście o intrygującym tytule The Tau Manifesto.

Postulat zastąpienia liczby – chyba najbardziej znanej stałej, występującej w matematyce, fizyce, grafice komputerowej i generalnie każdej dziedzinie wiedzy, mającej cokolwiek wspólnego z liczeniem czegokolwiek – wygląda zrazu na zupełnie szalony. Tym niemniej Manifest Tau zawiera naprawdę sporo argumentów przemawiających za tezą, że jednak jest bardziej użyteczną liczbą i lepiej spełnia funkcję “stałej okręgu” niż jej połówka, czyli . Ich podsumowanie wygląda mniej więcej tak:

1. Definicja jest nienaturalna, bo wykorzystuje pojęcie średnicy okręgu zamiast jego promienia. Promień jest tu lepszy w tym sensie, że okrąg można zdefiniować jako zbiór punktów w równej odległości od swojego środka – odległości równej właśnie promieniowi.
2. we wzorach matematycznych występuje często z czynnikiem 2 – na tyle często, że można stwierdzić, iż właśnie jest ważniejszą wartością niż samo .
3. Standardowa miara kątów płaskich w radianach przypisuje kątowi pełnemu, czyli kątowi jednego obrotu po okręgu. Przy użyciu kąt ten wyraża się jako , co wydaje się znacznie bardziej intuicyjne. Łatwiej jest też podobno wytłumaczyć, że np. ćwiartka okręgu to , a nie .
4. Słynna tożsamość Eulera (  ), łącząca pięć ważnych stałych matematycznych, ma też swój odpowiednik w postaci wykorzystującej : .
5. Wzór na pole koła (  ), w którym występuje z czynnikiem 1, po przepisaniu na staje się podobny do niektórych wzorów fizycznych (zwanych tutaj formami kwadratowymi), jak np. czy .

W oryginalnym artykule argumenty te przedstawione są rzecz jasna w sposób znacznie bardziej pomysłowy, elokwentny i trącący przekazywaniem “oczywistej oczywistości”, że się tak kolokwialnie wyrażę :) Trąci też jednak nadmiernym zamiłowaniem do numerologii i przywiązywaniem wagi to takich rzeczy jak czynnik przy jakiejś stałej w tym czy innym wzorze. Lecz nawet jeśli przyjmiemy tę konwencję, to znalezienie przekonujących kontrargumentów wcale nie jest trudne.

le ciste be fi lo’i namcu bei bau la lojban.

System liczb w lojbanie.

Jako kolejny temat odnośnie lojbanu zdecydowałem się opisać jego system numeryczny, czyli sposób wyrażania liczb. W dużym stopniu zainspirował mnie do tego pewien komentarz stwierdzający, że w lojbanie – biorąc pod uwagę jego nietypowość – używa się pewnie liczb Churcha albo innej, równie pokręconej konstrukcji :) Pewnie byłoby to jakoś zgodne z jego ideą, ale na szczęście w rzeczywistości jest zupełnie inaczej ;P

Zacznijmy od prostych cyfr, które to przedstawia poniższa tabelka:

Powinna ona od razu wzbudzić przyjazne uczucia, jako że wyraźnie pokazuje wielce interesujący fakt: lojban ma natywne wsparcie dla systemu szesnastkowego! I chociaż domyślnie używanym jest nadal ten dziesiętny, taka zapobiegliwość u twórców języka jest z pewnością godna uznania ;)

Nie bez powodu też ciągle używam pojęcia ‘cyfr’ zamiast ‘liczb’. Tak jak notacji matematycznej, liczby w lojbanie składa się bowiem z cyfr, i to dokładnie w ten sam, pozycyjny sposób. Powyższy zestaw słówek (są to oczywiście cmavo) jest wobec tego zupełnie wystarczający do wyrażenia każdej skończonej liczby naturalnej; nie ma żadnych osobnych form gramatycznych dla dziesiątek czy setek. Oto przykłady, które powinny ukazywać dokładną analogię między zapisem dziesiętnym a słownym w lojbanie:

Przy liczbach sięgających dziesiątek czy setek milionów pomocny jest separator ki’o, który jest oddziela tysiące (podobnie jak spacja w języku polskim lub przecinek w angielskim). Tak więc 4096 to vo ki’o nosoxa, a ilość bajtów w megabajcie (czyli 1048576) wyrazimy jako pa ki’o novobi ki’o muzexa. Przy okazji nadmienię, że spacje w zapisie tekstowym mogę wstawiać między cyframi w dowolny sposób (również nigdzie), co dotyczy zresztą każdego ciągu cmavo w lojbanie.

Co z większymi zbiorami liczb, jak całkowite czy wymierne? Mamy oczywiście znak minus, pozwalający tworzyć liczby ujemne: ni’u (dla spójności istnieje też znak plus: ma’u). Do ułamków niezbędny jest z kolei separator dziesiętny pi, którego nie należy mylić z liczbą π (ona sama ma zresztą swoje własne oznaczenie: pai). Wreszcie, jest też kreska ułamkowa, czyli fi’u. Przy pomocy tych słów możemy już wyrazić całkiem sporo różnych liczb:

Na tym zestawie chwilowo zakończymy, mimo że lojban posiada gramatykę “obsługującą” nawet liczby zespolone (!). Ciekawsze będzie raczej pokazanie sposobu użycia liczb w wypowiedzi. W ‘normalnych’ językach liczby służą zazwyczaj do określania ilości czegoś, najczęściej w sztukach. Dość podobnie jest w lojbanie, gdzie możemy liczbą opatrzyć sumti, jak w poniższym przykładzie:

mi renro vo rokci
Rzucam czterema kamieniami.

Jako ciekawostkę mogę dodać, że powyższe bridi nie specyfikuje tego, czy były to cztery osobne rzuty czy też jeden rzut wszystkimi czterema kamieniami naraz. Możliwe jest aczkolwiek dokładniejsze określenie, ale oczywiście nie będę się tym zajmował :)

loi patlu

Drugi sposób użycia liczb to sytuacje, gdy stanowią one samodzielne sumti. Dzieje się to nieco częściej niż w innych językach, gdzie zdania typu “Dwa plus dwa równa się cztery.” są relatywnie niezbyt powszechne poza samą matematyką. Tutaj jest trochę inaczej między innymi z tego względu, że użycia wszelkich jednostek miar – takich jak metry czy kilogramy – odbywają się za pośrednictwem odpowiadających im predykatów (czyli selbri), na przykład takich jak ten:

grake :: x₁ ma masę x₂ gramów wg standardu x₃

Miejsce (“argument”) x₂ wymaga tutaj właśnie liczby jako samodzielnego sumti. Tworzymy go za pomocą rodzajnika li. Stąd mamy np. li revo – liczba 24, a także:

loi patlu poi mi te vecnu cu grake li cinono
Ziemniaki, które kupiłem, ważą 500 gramów.

Tym, jak mógłby wyglądać dialog w sklepie, który do tego zakupu doprowadził, być może zajmę się w przyszłości :)

Zasada gołębiej dziury

Dzisiejsza notka będzie o pewnej matematycznej ciekawostce, która pokazuje, że nawet pozornie oczywiste stwierdzenie mogą mieć daleko idące konsekwencje, jakich nie da się na pierwszy rzut oka przewidzieć. Mamy mianowicie pewną kombinatoryczną regułę, mówiącą (w jednej z wersji), że:

Jeżeli n obiektów umieścimy w m < n pudełkach, to znajdzie się pudełko zawierające więcej niż jeden obiekt.

Zaskakujące, prawda? ;-) Wydaje się, że niewiele jest rzeczy bardziej oczywistych. A jednak powyższe twierdzenie doczekało się swojej własnej nazwy – i to nawet takiej, która uwzględnia nazwisko odkrywcy! W języku polskim mówimy mianowicie o zasadzie szufladkowej Dirichleta, a analogią jest podobno układanie skarpetek w szufladach. W angielskim z kolei używa się do tego… gołębi, a reguła jest znana jako pigeonhole principle – w dosłownym tłumaczeniu ‘zasada gołębiej dziury’.

Co jest niezwykłego w tak prostej obserwacji? Otóż jej wyjątkową cechą jest to, że stosuje się do wręcz nieograniczonego spektrum zjawisk różnego typu i wielu dziedzin, pozwalając udowadniać prawdziwość mnóstwa czasami zaskakujących stwierdzeń. Ich ciężar gatunkowy może się wahać od zabawnych, aczkolwiek pouczających, aż do zupełnie kluczowych dla niektórych dziedzin nauki. Oto przykłady:

• Struktury danych oparte na haszowaniu zawsze muszą uwzględniać metody rozwiązywania kolizji. Ten znany fakt jest konsekwencją tego, iż liczba możliwych kluczy n przekracza (zazwyczaj znacznie) rozmiar pojemnika m, więc nawet przy najlepszej funkcji haszującej znajdą się takie dwa klucze, które zostaną przyporządkowane w to samo miejsce.
• W pudełku jest 5 czarnych i 5 białych kul. Ile co najmniej kul musimy wybrać, żeby wśród nich znalazła się para tego samego koloru? Nie, wcale nie sześć – wystarczą trzy. Skoro mamy m = 2 kolorów, to już n = 3 kul gwarantuje, że będzie wśród nich para tego samego koloru.
• Wśród wszystkich obecnie żyjących ludzi co najmniej dwójka wypowiedziała w ciągu swojego dotychczasowego życia identyczną liczbę słów. Nawet gdyby ktoś paplał 24 godziny na dobę z prędkością jednego słowa na sekundę, w ciągu jednej doby nie powie ich więcej niż 86.400. Najstarszy człowiek miał/ma około 130 lat, w związku z czym ilość możliwych wartości dla wielkości ‘liczba wypowiedzianych słów’ to ok. 86.400 * 365,25 * 130, czyli nieco ponad 4 miliardy. Ponieważ na Ziemi żyje obecnie ponad 6 miliardów ludzi – czyli więcej – na mocy zasady szufladkowej wnioskujemy, że musi istnieć co najmniej dwójka, która wypowiedziała w ciągu życia tę samą liczbę słów.
• Jeśli algorytm kompresji bezstratnej rzeczywiście kompresuje (tj. zmniejsza objętość przynajmniej jednego pliku), to istnieje dla niego taki plik, który po “kompresji” będzie większy niż przed nią. Innymi słowy, nie ma doskonałych metod kompresji i nawet rosyjscy hakerzy nic na to nie poradzą :) Jest to bowiem bezpośrednia konsekwencja zasady ‘gołębiej dziury’.
  Powiedzmy, że najmniejszy plik faktycznie kompresowany (tj. zmniejszany) przez nas algorytm ma początkowy rozmiar , zaś po kompresji jest to już , gdzie . Istnieje skończona liczba plików rozmiaru , którą oznaczymy . (Jeśli na przykład jest to rozmiar w bajtach, to ). Z założenia żaden z tych plików nie zmienia rozmiaru podczas kompresji, więc ich wielkość po skompresowaniu to również . Oznacza to jednak, że tych plików to wyniki kompresji plików, bo także (większy niż ) jest kompresowany do jednego z tych plików. Ponieważ , na mocy zasady szufladkowej istnieją dwa takie pliki – mianowicie i jakiś plik rozmiaru – które są kompresowane do tego samego pliku wyjściowego. Jeśli tak jest, to algorytm nie może być bezstratny – czyli mamy sprzeczność, Q.E.D. :-)

Całkiem sprytne, nieprawdaż? Jak na zupełnie “oczywistą oczywistość”, zasada szufladkowa wykazuje niezwykłą użyteczność w wielu zaskakujących momentach. Warto o niej pamiętać nie tylko podczas poszukiwań pary pasujących skarpetek :)

Pr0centy

Jako że akurat trwa dla mnie okres najbardziej lubiany przez każdego studenta – czyli sesja – niespecjalnie miałem ostatnio czas na napisanie czegoś interesującego. Wiem, że niektórzy prowadzą bloga w ten sposób, że co kilka tygodni zamieszczają notkę o tym, dlaczego tak długo nie pisali… ale jakoś ta formuła niespecjalnie do mnie przemawia ;-)
Dlatego dzisiaj z braku lepszych pomysłów pozwolę sobie na mały off-topic, który aczkolwiek nawiązuje nieco do kilku wcześniejszych wpisów o tym, jak niektóre proste koncepcje matematyczne bywają źle używane i rozumiane. Tym razem rzecz dotyczy pojęcia niby trywialnego – procentów.

Wszyscy oczywiście wiedzą, co to znaczy, że jedna wielkość stanowi określony procent drugiej – mam nadzieję, że w celu zdobycia tej wiedzy wciąż wystarczy skończyć jedynie podstawówkę. O ile więc zastosowanie procentów w celu wyrażenia relacji zwykle nie sprawia nikomu kłopotów, o tyle znacznie powszechniejsze ich użycie – do opisywania wzrostów i spadków, czyli zmian jakichś wielkości w czasie – już niezupełnie.
Co mam tutaj na myśli? Weźmy klasyczny przykład “handlowy”, w którym cenę jakiegoś towaru wpierw podniesiono, a następnie obniżono o 20 procent. Czy plus dwadzieścia i minus dwadzieścia to razem zero?… Naturalnie nie, bo wartość procentowa zawsze występuje w relacji do jakiejś całości – w tym przypadku do aktualnej ceny. Jeśli wynosiła ona na początku x, to po tych dwóch operacjach będzie równa:

Spadnie więc o 4%. W uproszczeniu można zatem powiedzieć, że “procenty nie dodają się”, chociaż trzeba oczywiście pamiętać, co się za tym stwierdzeniem kryje.
Może to zaskakujące, ale sprawa pośrednio dotyczy też… gamedevu, a zwłaszcza gier strategicznych i RPG, gdzie często występują różne efekty procentowe (np. zwiększenie obrażeń jednostki o x%), z których kilka może być aktywnych naraz. Ich “składanie” niekiedy jest zaimplementowane dobrze (tak jak powyżej), a niekiedy źle, co często daje się łatwo zauważyć.

Druga kwestia to opisywanie zmian takich wielkości, które same są wyrażone w procentach, jak tempa wzrostu (np. gospodarczego) lub udziału czegoś w całości (np. programów napisanych w danym języku w stosunku do wszystkich). Trzeba pamiętać, że nawet w takich przypadkach procenty zawsze oznaczają relację całość-część, niezależnie od tego w jakich jednostkach owa całość jest wyrażana.
Oto przykład: w pewnym kraju wzrost PKB dwa lata temu wynosił 2%, a w poprzednim roku już 3%. O ile (procent) się zmienił?… Oczywiście o:

.

Jak nietrudno bowiem zauważyć, wzrósł o połowę. Chcąc ten fakt wyrazić w wielkościach bezwzględnych powinniśmy natomiast powiedzieć, że różnica wynosiła jeden punkt procentowy. Stwierdzenie, że jest ona równa 1% znaczyłoby bowiem tyle, że chodzi nam o jeden procent od wartości ‘2’, co rzecz jasna nie jest prawdą.