Napisz program asemblujący GOLF , który odczytuje liczbę całkowitą ze standardowego wejścia (po którym następuje końcowy znak nowej linii), i wyświetla swoje czynniki pierwsze oddzielone znakami nowej linii, a następnie na końcu standardowego znaku nowej linii.
Czynniki pierwsze nie muszą być w określonej kolejności. 1
nie jest głównym czynnikiem.
Twój plik binarny GOLF (po złożeniu) musi mieścić się w 8192 bajtach.
Twój program zostanie oceniony, uruchamiając go 10 razy, każdy z jednym z następujących danych wejściowych:
8831269065180497
2843901546547359024
6111061272747645669
11554045868611683619
6764921230558061729
16870180535862877896
3778974635503891117
204667546124958269
16927447722109721827
9929766466606501253
Liczby te są z grubsza posortowane według stopnia trudności. Pierwszy powinien być łatwy do rozwiązania przez podział próbny.
Optymalizacja w kierunku tego zestawu liczb jest sprzeczna z duchem pytania, mogę zmienić zestaw liczb w dowolnym momencie. Twój program musi działać na każdą dodatnią 64-bitową liczbę wejściową, nie tylko na te.
Twój wynik to suma cykli procesora użytych do uwzględnienia powyższych liczb.
Ponieważ GOLF jest bardzo nowy, dołączę tutaj kilka wskazówek. Należy zapoznać się z GOLF specyfikacji ze wszystkimi instrukcjami i kosztów cyklu . W repozytorium Github można znaleźć przykładowe programy. W szczególności spójrz na przykładowy program czynnikowy , który demonstruje wejście / wyjście.
Skompiluj swój program do pliku binarnego, uruchamiając python3 assemble.py your_source.golf
. Następnie uruchom program za pomocą python3 golf.py your_source.bin
, powinno to również wydrukować liczbę cykli. Zobacz wartości zawartości rejestru przy wyjściu programu z -d
flagą - użyj, --help
aby zobaczyć wszystkie flagi.
1
nie jest to czynnik główny, czy powinien wypisywać tylko całkowitą liczbę wejściową?Odpowiedzi:
2279635 cykli - 7373 bajtów (deterministycznych)
Jeden po drugim:
Podsumowanie:
Używam kombinacji podziału próbnego i algorytmu rho Brenta-Pollarda do faktoryzacji i wyszukiwania tabeli oraz Millera-Rabina do testowania pierwotności. Jutro dodam więcej wyjaśnień.
Zauważ, że ze względu na limit znaków długości postów druga tabela danych jest obcinana. Ta lista zawiera pełny stół.
źródło
mov o, 42
jest martwa gratka.Ogółem 36 757 269 913 cykli
830B zmontowane
Faktoryzacja według podziału próby, z kilkoma optymalizacjami. Prawdopodobnie nie najszybszy, ale ponieważ nikt jeszcze tego nie napisał, zacznę.
Pełny wynik z mojej pętli czasowej, na wypadek, gdyby ktoś chciał sprawdzić wyniki i / lub skopiować i wkleić i matematykę.
źródło
divu
: stackoverflow.com/questions/5558492/... . Co do twojej odpowiedzi - to pytanie nie miało być rozwiązane za pomocą podziału próbnego: Pfactor * factor < number
- żadna liczba nie może mieć czynników większych niż pierwiastek kwadratowy.wynik = 378,867,816 cykli
[losowo - Twoje wyniki mogą się różnić]
Wykorzystuje test pierwotności Millera-Rabina (wersja deterministyczna, która może obsłużyć do 2 ^ 64), trochę faktoringu próbnego i faktoring ECM . Są tam wszystkie operacje algebraiczne, w tym modułowe dodawanie, odejmowanie, mnożenie, potęgowanie i inwersja (mod n <2 ^ 64).
Mnożenie modułowe jest nieoptymalne - wyszukuje binarnie iloraz. Obliczenie pozostałej części podziału 128 przez 64 jest trudne bez zgodnej instrukcji wbudowanej. Przyspiesz to, a wszystko pójdzie szybciej.
Skompilowano 2290 bajtów
Wydajność:
źródło