TMUL – Not so fast multiplication

Implementując szkolne mnożenie pisemne nie da się rozwiązać tego zadania w czasie oczekiwanym przez spoj, nawet stosując obliczone wcześniej tablice modulo i mnożenia (próbowałem!).

 

Tutaj nie ma sensu wymyślanie własnego alogorytmu, conajwyżej można napisać własną implementację jednego z najszybszych znanych algorytmów:

 

1) Schönhage-Strassen SSA
2) Tom-Cook
3) Karatsuba – Karatsuba c implementation
4) FFT  –   Mutliplication using fft

 

Warto pamiętać że każdy z tych algorytmów ma swój przedział w którym jest najlepszy, ale dla tego zadania wszystkie powyższe będą ok.

 

Zadanie można submitować również w Javie, a ta w klasie BigInteger udostępnia metodę multiply() która dopasowuje rozmiar podanych liczb do najszybszych znanych algorytmów, ale to trochę mało dydaktyczne.

 

Źródła:
Przydał się parę razy do testów:
Rozpisanie istniejących algorytmów:
1)
Advertisements

PA05_POT Czy umiesz potęgować

Zadanie trzeba było rozwiązać zauważając powtarzalność ostatniej cyfry potęgowanej liczby, zwykłe potęgowanie byłoby zbyt złożone obliczeniowo dla podanego zestawu.

Jak zauważyć powtarzalność? Kartka papieru, rozpisać ostatnie cyfry dla 0^1, 0^2, …., 1^1, 1^2, 1^3, …, 9^5 itd.

Potem zapisać odpowiednią tabelę w kodzie, tak aby program sięgał jedynie po odpowiednią wartość z tabeli, zamiast obliczać.

To jak długo wykonuje się progam można sprawdzić pod linuxem za pomocą polecenia ‘time’, np. ‘time wget google.com’, jeśli ktoś chce porównać zwykłą implementację z tą z opisanym chwytem.

Można tu jeszcze użyć stdlib lub wyłączyć synchronizację io w iostream, ale to drobiazgi.

Kod:

#include <iostream>

using namespace std;

int main() {

    unsigned short results[10][1][4] = {{{0}},{{1}},{{6,2,4,8}},
{{1,3,9,7}},{{6,4}},{{5}},{{6}},{{1,7,9,3}},{{6,8,4,2}},{{1,9}},};

    unsigned short modulo[] = {1, 1, 4, 4, 2};

    long n;
    cin >> n;

    long cases[n][2];

    for (long a = 0; a < n; a++)
        cin >> cases[a][0] >> cases[a][1];

    for (long a = 0; a < n; a++) {

        unsigned short moduloDivisorIndex = (cases[a][0] % 5);
        unsigned short moduloDivisor = modulo[moduloDivisorIndex];
        unsigned short lastDigit = cases[a][0] % 10;
        long moduloIndex = cases[a][1] % moduloDivisor;

        cout << results[lastDigit][0][moduloIndex] << '\n';
    }

    cout << endl;

    return 0;
}

Wersja z komentarzem:

#include <iostream>

using namespace std;

int main() {

    //1 indeks jaka jest ostatnia cyfra podstawy
    //3 jaki jest wynik modulo przez komórkę z modulo[]
    unsigned short results[10][1][4] = {
            {       //0
                    {0}
            },{
                    //1
                    {1}
            },{
                    //2
                    {6, 2, 4, 8}
            },{
                    //3
                    {1, 3, 9, 7}
            },{
                    //4
                    {6, 4}
            },{
                    //5
                    {5}
            },{
                    //6
                    {6}
            },{
                    //7
                    {1, 7, 9 ,3}
            },{
                    //8
                    {6, 8, 4, 2}
            },{
                    //9
                    {1, 9}
            },
    };

    unsigned short modulo[] = {1, 1, 4, 4, 2};

    //Pattern na modulo: 1 4 4 2 1
    //Modulo przez 5
    //Dla 1 - 1
    //Dla 2 - 4
    //Dla 3 - 4
    //Dla 4 - 2
    //Dla 0 - 1

    //Liczba: 1
    //Potęgi 1 2 3 4 5 6 7 8 9
    //Wyniki:1 1 1 1 1 1 1 1 1
    //Powtarzanie: [1]

    //Liczba: 2
    //Potęgi 1 2 3 4  5  6  7   8   9
    //Wyniki:2 4 8 16 32 64 128 256 512
    //Powtarzanie: [2 4 8 6]
    //Modulo przez 4:
    //1 - 2
    //2 - 4
    //3 - 8
    //0 - 6

    //Liczba: 3
    //Potęgi 1 2 3  4   5
    //Wyniki:3 9 27 81  243
    //Powtarzanie: [3 9 7 1]
    //Modulo przez 4:
    //1 - 3
    //2 - 9
    //3 - 7
    //0 - 1

    //Liczba: 4
    //Potęgi 1 2  3  4    5
    //Wyniki:4 16 64 256  1024
    //Powtarzanie: [4 6]
    //Modulo przez 2:
    //1 - 4
    //0 - 6

    //Liczba: 5
    //Potęgi 1 2  3   4
    //Wyniki:5 25 125 625
    //Powtarzanie: [5]
    //Modulo przez 1:
    //0 - 5

    //Liczba: 6
    //Potęgi 1 2  3   4
    //Wyniki:6 36 216 1296
    //Powtarzanie: [6]
    //Modulo przez 1:
    //0 - 6

    //Liczba: 7
    //Potęgi 1 2  3   4    5
    //Wyniki:7 49 343 2401 16807
    //Powtarzanie: [7 9 3 1]
    //Modulo przez 4:
    //1 - 7
    //2 - 9
    //3 - 3
    //0 - 1

    //Liczba: 8
    //Potęgi 1 2  3   4    5
    //Wyniki:8 64 512 4096 32768
    //Powtarzanie: [8 4 2 6]
    //Modulo przez 4:
    //1 - 8
    //2 - 4
    //3 - 2
    //0 - 6

    //Liczba: 9
    //Potęgi 1 2  3   4    5
    //Wyniki:9 81 729 6561 59049
    //Powtarzanie: [9 1]
    //Modulo przez 2:
    //1 - 9
    //0 - 1

    //Liczba: 10
    //Potęgi 1
    //Wyniki:10
    //Powtarzanie: [0]
    //Modulo przez 1:
    //0 - 0

    long n;
    cin >> n;

    long cases[n][2];

    for(long a =0;a<n;a++)
        cin >> cases[a][0] >> cases[a][1];

    for(long a =0;a<n;a++){

        unsigned short moduloDivisorIndex = (cases[a][0] % 5);
//        cout << "Modulo divisor index: " << moduloDivisorIndex << endl;

        unsigned short moduloDivisor = modulo[moduloDivisorIndex];
//        cout << "Modulo divisor: " << moduloDivisor << endl;

        unsigned short lastDigit = cases[a][0] % 10;
//        cout << "Last digit: " << lastDigit << endl;

        long moduloIndex = cases[a][1] % moduloDivisor;
//        cout << "Modulo index: " << moduloIndex << endl;

        cout << results[lastDigit][0][moduloIndex] << '\n';
    }

    cout << endl;

    return 0;
}

Sound processing X – Tymczasowe problemy

Zapowiedzianego w ostatnim poście pierwszego próbnego gameplayu nie będzie:

Pomimu kilku prób, mój ThinkPad nie potrafił wydusić z siebie wystarczająco głośnego dźwięku, aby drugi komputer mógł go z powodzeniem odczytać, kończyło się tak, że transmisja była dobra, pomijając w kilku miejsach źle przesłaną cyfrę, co jeśli chodzi o znaki ASCII kończyło się wstawieniem np. znaku pi zamiast dwukropka i w efekcie złym sparsowaniem jsona (modem jest na tyle dobry, że praktycznie zawsze nadawca podsłuchując to co wysyła potrafi to z powrotem sparsować, więc kwestią zostaje głośność).

Prawdopodobnie mógłbym to rozwiązać mikrofonami kierunkowymi, chociaż pozostałby niesmak, że to już nie jest tym, czym było w zamierzeniach (transmisja z urządzenia na urządzenie, bez internetu i specjalnych przyrządów).

Tak czy inaczej, projekt będzie kontynuowany, mam zamiar zakupić pierwszy lepszy kierunkowy mikrofon x2 i nagrać jakiś film, a na ten moment szukam innego wyjścia, w końcu ktoś już napisał podobne aplikacje:

Możliwe, że to kwestia zejścia poziom niżej i napisania własnego wykrywania częstotliwości na podstawie DFT, co nie byłoby takie złe.

W weekend powinien pojawić się nowy post, bo nie sądzę, żebym trafił na ścianę nie do przejścia.


dsp2017-1

Różne V – Sphinx i rozpoznawanie mowy

Jak już wspominałem przy okazji posta z serii Pokaż kod, pisząc Speechlist, na początku byłem nastawiony na rozwiązywanie testów głosem. Częściowo mi się to udało, chociaż przeniesienie tego na telefon nie było łatwe, żeby nie powiedzieć – sprawiało kłopoty, dlatego finalnie je porzuciłem na rzecz zwykłego wstawiania tekstu dotykiem. Zostałem z częściowo już napisanym frontendem pod rozpoznawanie głosu, możecie go zobaczyć w działaniu tutaj:

Kod Speechlist udostępniłem za darmo pod adresem: https://bitbucket.org/dbeef/speechlist

Nie rozpisałem się wtedy co do samego Sphinxa, a to jest temat na większy post.

Czym jest CMUSphinx

CMUSphinx jest opensourcowym narzędziem do rozpoznawania mowy, wspierające C, C++, C#, Python, Ruby, Java, Javascript i rozpoznające m.in. angielski, francuski i niemiecki (chociaż społeczność zbudowała modele rozpoznające także chociażby rosyjski, lista modeli do pobrania jest tutaj).

Wielkim plusem w stosunku chociażby do androidowych usług rozpoznawnia głosu (komunikujących się z serwerami Google) z których można korzystać pisząc aplikacje jest to, że Sphinx działa całkowicie offline.

Do jego działania potrzebne są 3 pliki: acoustic model, dictionary i language model.

Acoustic model zależy od języka i sami go raczej nie stworzymy, pobieramy gotowy z listy którą zamieściłem wyżej. Przykładowo, dla języka angielskiego pobieramy model en-us.

Language model i dictionary generujemy sami za pomocą narzędzi do których odniosę się później, ale można je także pobrać.

Teraz najważniejsze: aby uzyskać niemal 100% skuteczność rozpoznawania, jak na filmiku wyżej, nie używałem gotowego słownika i modelu językowego z ich strony (zawierającego wszystkie słowa). CMUSphinx udostępnia narzędzie, pozwalające zbudować słownik tylko konkretnych słów:

http://www.speech.cs.cmu.edu/tools/lextool.html

Dzięki temu, że zamieściłem tam tylko te słowa, które muszą być rozpoznane w Speechlistowym teście, poprawność była tak dobra, że trudno uwierzyć.

Przy tym wszystkim warto też dodać, jak niewiele zasobów wymaga Sphinx. Słowniki i modele ważą tyle co nic, a działanie nie wymaga dużej mocy od komputera.

PocketSphinx z którego korzystam na filmiku i w kodzie poniżej, waży 6.7 kB!

https://bitbucket.org/dbeef/speechlist/src/990c18c459d5f6b89971fc6b93d24fa4730ba07f/android/libs/pocketsphinx.jar?at=master&fileviewer=file-view-default

Praktyka

Wykorzystanie Sphinxa w przykładzie z filmiku wygląda następująco:

Tworzymy obiekt edu.cmu.sphinx.api.Configuration, aby załadować z plików modele i słowniki.

configuration

Tworzymy obiekt edu.cmu.sphinx.api.LiveSpeechRecognizer, dostarczamy mu konfigurację w konstruktorze i stawiamy warunek który skończy rozpoznawanie mowy (np. while(!lastRecognizedWord.equals(“apple“)), w poniższym przykładzie rozpoznawanie trwa przez cały czas (while(true)).

sphinx2

To wszystko. Teraz, we frontendowej części kodu odczytujemy zapisane przez Sphinx słowa i wyświetlamy na ekranie:

frontend

Cały plik znajduje się pod adresem:
 https://bitbucket.org/dbeef/speechlist/src/990c18c459d5f6b89971fc6b93d24fa4730ba07f/core/src/com/dbeef/speechlist/recognition/SpeechRecognizer.java?at=master&fileviewer=file-view-default

 

Linki:

Repozytorium Speechlist (branch master jest pod rozpoznawanie mowy):

https://bitbucket.org/dbeef/speechlist/src/990c18c459d5?at=master

Artykuł opisujący dostosowywanie CMU pod język polski:

 https://www.researchgate.net/publication/282323232_Tuning_a_CMU_Sphinx-III_speech_recognition_system_for_Polish_language

Dla szukających więcej informacji na temat słowników:

https://cmusphinx.github.io/wiki/tutorialdict/

Mam jednak zastrzeżenie co do ich słów:

There is no need to remove unused words from the dictionary unless you want to save memory, extra words in the dictionary do not affect accuracy.

Z moich doświadczeń wynika, że jest zupełnie odwrotnie. Przekonajcie się sami, zapiszcie sobie kilka słów na kartce, które chcecie wypróbować na Sphinxie, pobierzcie cały słownik z ich strony, wypróbujcie dokładność, a potem zróbcie to samo generując własny za pomocą ich narzędzia, ale wstawiając do niego tylko te słowa, które potem będziecie wymawiać.


dsp2017-1

Robimy MMOSG I – Wstęp i research.

 

tldr: Nowa seria – robimy ogame.


Ostatnio dla zabawy próbowałem stworzyć lekki webowy frontend do bazy danych (z losowo wygenerowanymi użytkownikami) przy użyciu JQuery i Spring Boota z MongoDB po stronie serwera. Całkiem i się to spodobało i teraz w głowie mam większy pomysł, czyli stworzenie chociaż najbardziej badziewnego, ale działającego massively multiplayer online strategic game (ogame/plemiona/ikariam etc). Bazy danych + technologie webowe wyglądają znacznie lepiej w parze, jeśli patrzeć pod kątem CV, a wydaje mi się że zasadniczo dobrze jest umieć na jakimś poziomie zwizualizować backend. Zacznijmy więc może od przedstawienia kilku problemów które będą po drodze.

Problemy i research

W jaki sposób serwer będzie wiedział, kiedy może odesłać przeglądarce stronę dostępną tylko dla zalogowanych, a kiedy nie, a bardziej ogólnie: skąd wie, czy użytkownik jest zalogowany?

Z tego co wygooglowałem i sam się domyśliłem, wygląda to tak:

Użytkownik loguje się pomyślnie na stronie (hash hasła z jego formularza pokrywa się z tym w bazie danych), na serwerze zostaje wygenerowany unikatowy token i zapisany w bazie danych razem z adresem IP osoby która się zalogowała a także datą wygaśnięcia tokena. Do tej samej osoby, odsyłany jest token, zapisywany jest w formie ciasteczka, a następnie kiedy tylko ta osoba zażąda strony, która dostępna jest tylko dla zalogowanych, serwer porówna token przesłany z ciasteczek oraz adres IP, jeśli wszystko się zgadza, to odsyła stronę, jeśli nie, redirect na stronę logowania.

Na co warto rzucić okiem:

https://pl.wikipedia.org/wiki/HTTP_cookie

https://blog.risingstack.com/web-authentication-methods-explained/

https://security.stackexchange.com/questions/755/how-does-basic-http-auth-work

http://viralpatel.net/blogs/spring-mvc-cookie-example/ 

http://stackoverflow.com/questions/12050059/user-session-tracking-in-javascript

Trzymanie haseł

Minimum bezpieczeństwa, czyli trzymanie hashy. Samo przesyłanie informacji z przeglądarki na serwer również powinno być jakoś zabezpieczane:

https://stackoverflow.com/questions/4101440/jquery-sending-password-via-ajax

https://www.owasp.org/index.php/Cross-Site_Request_Forgery_%28CSRF%29_Prevention_Cheat_Sheet

Wygląd strony

Jestem w tym zielony (nie znam niczego poza CSS, HTML), ale póki co nie przejmuję się tym, frontend wyjdzie po drodze i będę wyszukiwał na bieżąco gdy tylko znajdzie się czas. Co do tego, znalazłem całkiem fajną stronę:

https://uptodate.frontendrescue.org/

Materiały do nauki

Okazuje się, że w sieci jest całkiem sporo opensourcowych klonów Ogame, przykładowa lista:

https://freevps.us/thread-7746.html

W razie problemów, będe zaglądał w kod.


Oczywiście wszystko krok po kroku, zanim dojdziemy do pierwszego prototypu minie czas i jestem świadom że nie zrobię wszystkiego powyższego w jeden weekend.

Gdy zaczniemy pisać kod do tej serii, udostępnię go na moim Githubie:

https://github.com/dbeef


dsp2017-1

 

Sound processing IX – Udało się!

tldr: Nadawanie wiadomości z wewnątrz gry i odbieranie jej stamtąd działa pełną parą. Pozostało zaimplementować rozgrywkę z prawdziwego zdarzenia i podsumować serię w okrągłych dziesięciu postach.


Rozwiązanie problemu z głośnikami

Przekopałem całą dokumentację Beads, nie znalazłem niczego co wskazywałoby na problem albo chociaż pozwalało nadać wszystko ciągiem – znalazłem jednak możliwość zapisywania wygenerowanych częstotliwości jako plik .wav i… bingo.

Zapisuję każdą jedną z częstotliwości dotychczas już generowanych na dysku (każda po ~32.kB) , po czym łączę je w jeden duży (5.8 MB) plik i odtwarzam wewnątrz Mad Pirates. Takich mniejszych plików jest 188, wygenerowanie ich zajmuje około 6 sekund.

Screenshot from 2017-05-27 21-27-10.pngWygenerowane pliki.

Odtworzenie całej wiadomości jako plik .wav nie stwarza najmniejszych problemów z głośnikami, więc największy problem transmisji jest już na dobre zamknięty.

Screenshot from 2017-05-27 21-31-57.pngKlasa FileMerger.java którą łączę powstałe pliki .wav.
filerecorder.pngKlasa FileRecorder.java która jest przerobionym tutorialem Beads ze strony:
https://github.com/orsjb/beads/blob/master/packages/Beads/beads_tutorial/Lesson09_RecordToSample.java

Emitowanie i nasłuchiwanie

Komputer musi w jakiś sposób wiedzieć, czy ta część wiadomości, którą do tej pory odebrał, nadaje się do parsowania. Rozwiązałem to, tworząc cyklicznie co sekundę nowy wątek próbujący sparsować obecny bufor z informacjami z głośników. Jeśli się nie powiedzie – trudno, exception, wątek ginie, tworzy się nowy i próbuje to samo. Jeśli się uda – transmisję uznajemy za udaną i podstawiamy wyniki ze sparsowanego obiektu do symulacji. Działa, ale niezbyt eleganckie. Do wymiany w przyszłości.

sounddecoder.png

Jeśli chodzi o emitowanie wiadomości, to skorzystałem ze starej klasy StarterBroadcaster.java, która zamiast odtwarzać dźwięki, to zapisuje je, a po skończeniu tego procesu odczytuje główny plik ze zlepionymi dźwiękami – po wszystkim wątek się zamyka. StarterBroadcaster tworzony jest na żądanie, przyciskiem klawisza G.

Reorganizacja kodu

Do utrzymania porządku dopisałem kilka klas, m.in. FileLoader.java, z którego biorę referencje do tekstur które załadował, a także HUD.java, który trzyma wszystkie możliwe opcje wyświetlania interfejsu użytkownika, tj. tryb w którym wypisuje “Tura planowania”, tryb z wypisywaniem “Tura symulacji” i tak dalej. KeyboardInterpreter.java odpowiada za logikę przy wciskaniu klawiszy a InputModel.java został dodany dla łatwego transportu informacji pomiędzy klasami.

Nie do końca jestem zadowolony ze zmian (logika działania nadal nie jest do końca czytelna i można się pogubić w boolean-ach), ale na ten moment wystarczy.

Efekty

Oto zakończona sukcesem próba przesłania obecnej pozycji statku dźwiękiem (odbiorcą i nadawcą był ten sam komputer).

Co dalej

Aby uczynić owoce tej pracy użytecznymi, zamiast przesyłać pozycję XY statku będziemy przesyłać pozycję kliknięcia myszką gracza i do tego na start gry przyjmować w argumencie konsoli to, którym graczem gramy (wtedy obie strony wzajemnie znają początkową pozycję początkową siebie i przeciwnika) – tak właściwie, to już to zrobiłem, tym urywkiem kodu:
pozycje

Aby przetestować to rozwiązanie prosto w IDE, wystarczy wyedytować konfigurację startową:

konf

Jesteśmy na skraju celu, którym jest faktycznie móc się poruszać po planszy co turę, grając w dwie osoby, więc to już w następnym, podsumowującym poście.


Jak zawsze, kod dostępny jest na moim GitHubie:

https://github.com/dbeef/soundcoding

dsp2017-1