Python 3: Poznaj f-strings

O nowym, łatwiejszym sposobie interpolacji stringów – f-strings pisze Mike Driscoll 👌

#python #blog #technicalblog #programowanie

Jako, że trwa promocja na Helionie 2+1 na wybrane książki, to tu zestawiłam wartościowe książki do Pythona:
https://www.flynerd.pl/2018/0[...]-ksiazki-godne-polecenia.html
#python #książka

Dzisiaj świętujemy Dzień Informatyka !👩‍💻👨‍💻
Z tej okazji ⬇️obniżamy⬇️dla Was całą kategorię PROGRAMOWANIE o 30% 😉

https://videopoint.pl/go-promocja_programowanie

#programowanie #java #python #SQL #unity #Ruby #rubyonrails #promocje #naukaprogramowania

Różniczkowanie Symboliczne

Ha, ha, dawno już nie było teorii, wszyscy stęsknieni:P; to do roboty: Symbolic differentiation!
Temat jest bliski moim zainteresowaniom, tzn. AI; więc, studiując słynne PAIG plus (obowiązkowo!) SICP natkąłem się na jak w temacie.
Jako że ciężko mi było nadążyć z oryginalnym kodem w Lispie:

(defun deriv-poly (p x)
"Return the derivative, dp/dx, of the polynomial p."
" If P is a number or a polynomial with main-var > x,
" then p is free of x, and the derivative is zero;
" otherwise do real work.
" But first, make sure X is a simple variable,
" of the form #(X 0 1).
(assert (and (typep x 'polynomial) (= (degree x) 1)
(eql (coef x 0) 0) (eql (coef x 1) 1)))
(cond
« numberp p) 0)
«var> (main-var p) (main-var x)) 0)
(var= (main-var p) (main-var x))
d(a + bx + cx2 + dx3)/dx = b + 2cx + 3dx A 2
;; So. shift the sequence p over by 1. then
;; put x back in. and multiply by the exponents
(let «r (subseq pI)))
(setf (main-var r) (main-var x))
(loop for i from 1 to (degree r) do
(setf (coef r i) (poly*poly (+ i 1) (coef r i))))
(normalize-poly r)))
(t ;; Otherwise some coefficient may contain x. Ex:
d(z + 3x + 3zx2 + z2x3)/dz
;; = 1 + 0 + 3x2 + 2zx A 3
;; So copy p. and differentiate the coefficients.
(let «r (copy-poly p)))
(loop for i from 0 to (degree p) do
(setf (coef r i) (deriv-poly (coef r i) x)))
(normalize-poly r)))))

Plus pomoc z SICP (Scheme):

(define (deriv exp var)
(cond ((number? exp) 0)
((variable? exp) (if (same-variable? exp var) 1 0))
((sum? exp) (make-sum (deriv (addend exp) var)
(deriv (augend exp) var)))
((product? exp)
(make-sum
(make-product (multiplier exp)
(deriv (multiplicand exp) var))
(make-product (deriv (multiplier exp) var)
(multiplicand exp))))
(else
(error "unknown expression type: DERIV" exp))))

(Nawiasem pisząc, formatka 4programmers ssie (nie formatuje Lispu)), to wysmażyłem swój w Pythonie (kompilowalny pseudokod :-D). Idea jest prosta: Na najniższym poziomie - pochodna liczby jest zerem, pochodna zmiennej jest jedynką, jeśli to ta sama zmienna, zerem jeśli inna (jak stała). Problemem jest, jak to odwzorować w notacji infiksowej (jak Python i inne języki głównonurtowe). Okazuje się, że można wykorzystać algorytm parsowania formuły do (binarnego na razie!!) drzewa składniowego.
Idea: Pochodna sumy jest sumą pochodnych, a pochodna iloczynu, jest sumą iloczynu pierwszego członu razy pochodna drugiego plus pochodna pierwszego razy drugi; doskonale wpisuje się to w drzewo składniowe:

def evaluate(tree):
    opers = {'+': sym_add, '-': op.sub, '*': sym_mul, '/': op.truediv}
 
    leftT = tree.getLeftChild()
    rightT = tree.getRightChild()
 
    if leftT and rightT:
        fn = opers[tree.getRootVal()]
        return fn(evaluate(leftT), evaluate(rightT))
    else:
        return tree.getRootVal()
 
def evaluate_parse_tree(tree, var):
    opers = {'+': sym_add, '-': op.sub, '*': sym_mul, '/': op.truediv}
 
    leftT = tree.getLeftChild()
    rightT = tree.getRightChild()
 
    if leftT and rightT:
        fn = opers[tree.getRootVal()]
        # changes start:
        if fn is sym_mul:
            fn = sym_add
            return fn(sym_mul(evaluate(leftT), evaluate_parse_tree(rightT, var)), sym_mul(evaluate_parse_tree(leftT, var),
                    evaluate(rightT)))
        else:
            return fn(evaluate_parse_tree(leftT, var), evaluate_parse_tree(rightT, var))
    else:
        return derrive(tree.getRootVal(), var)
 
def derrive(exp, var):
    if is_number(exp): return 0
    elif is_variable(exp):
        return 1 if same_variable(exp, var) else 0

Dwie funkcje evaluate_parse_tree i evaluate działają zgodnie z powyższym schematem; chociaż widać tu dużo braków: Trzeba upraszczać końcowe wyrażenia (albo poprawić sym-add i sym_mul). Lecz pomysł działa. Kod (już nie GitHubie, bo go nie ma:-D), z funkcjami sym_add i tak dalej (w razie nieścisłości zapraszam do dyskusji) tutaj: https://bitbucket.org/lion137[...];fileviewer=file-view-default
Działa?

 form = "((1 + (2 * x)) * (1 + x))"
   p_tree = BinaryTree('')
   p_tree = build_parse_tree(form)
   print(evaluate_parse_tree(p_tree, "x"))# -> 1(1 + 2x) + (0 + 2 + 0x)*(1 + x)
   form = "(x + 1)"
   p_tree = BinaryTree('')
   p_tree = build_parse_tree(form)
   print(evaluate_parse_tree(p_tree, "x")) # -> 1

Jak widać tak (chociaż): Wyrażenie musi być poprawnie znawiasowane i forma wyniku przedstawia sporo do życzenia.
Ale droga jest właściwa! :-D)
#theory #Python

#theory #Python

11 blogów logów poświęconych Pythonowi, które warto odwiedzać.

Co jeszcze powinno znaleźć się w zestawieniu? 🤔

#blog #python #technicalblog

Nowości ze świata Pythona.
Dataclasses:
https://hackernoon.com/a-brie[...]3-7-data-classes-22ee5e046517
Python3 jest szybszy od 2.7 (wbrew niektórym opiniom, również na tym forum):
https://speed.python.org/changes/
Jest oficjalna data, odejścia od Legacy Pythona:
https://pythonclock.org/
W związku z tym dobry pomysł na biznes na przyszły rok, konsulting przy przechodzeniu z 2.7 na 3!:), Kurs, na przykład, tutaj:
https://www.pluralsight.com/courses/python-2-to-python-3
#python #Python #links

Faktoryzacja 2

Wypadałoby, poza naiwnym dzieleniem, jak tutaj dodać, jakieś efektwniejsze (ale jeszce w miarę proste) metody faktoryzacji. Na początek Pollard's Rho - artykuł jest jasny, jak ktoś chce poeksperymentować, to kod w Pythonie:

def rho(n):
    if miller_rabin(n):
        return n
    def g(x, m):
        return (x*x - 1) % m
    x = 2
    y = 2
    d = 1
    while d == 1:
        x = g(x, n)
        y = g(g(y, n), n)
        d = gcd(abs(x - y), n)
    if d == n:
        return False
    else:
        return d

Funkcja, nie zawsze musi zwrócić dzielnik pierwszy, w praktyce trzeba by ograniczyć liczę prób, a jest skuteczny gdy czynniki nie są duże; złożoność: O(n^1/4).

Do większych czynników Fermat, prosta obserwacja, że każda liczba nieparzysta jest równa różnicy dwóch kwadratów, prowadzi bezpośrednio do algorytmu, Python:

def fermat_factorization(n):
    def is_square(a):
        if a < 0:
            a = -a
        return int(sqrt(a)) * int(sqrt(a)) == a
    a = int(sqrt(n))
    b = a * a - n
    while not is_square(b):
        a += 1
        b = a * a - n
    return [a - int(sqrt(b)), a + int(sqrt(b))]

Ta zaś funkcja, przeciwnie do rho, zwraca najszybciej czynniki bliskie pierwiatkowi z n. Algorytmy się ładnie uzupełniają, mogłyby współpracować w faktoryzacji (najlepiej równolegle,).

Na koniec jeden z algorytmów faktoryzujących duże liczby(znowu Pollard) Pollard p -1 algorytm - artykuł tłumaczy jasno, kod(Python):

def pollard_p_minus_1(n, max_iter, b):
    """Performing Pollard p- 1 factorization,
    with odd number input"""
    for _ in range(max_iter):
        primes = prime_sieve(b)
        for i in range(len(primes)):
            primes[i] = primes[i] ** (int(log(n, primes[i])))
        m = reduce(op.mul, primes)
        g = gcd(modularexponenation(2, m, n) - 1, n)
        if 1 < g < n:
            return g
        if g == 1:
            b += (b // 5)
        if g == n:
            b -= (b // 5)

Początkowe b, a także ilość iteracji, trzeba dobrać, rekordy algorytmu tutaj: https://members.loria.fr/PZimmermann/records/Pminus1.html.
Dodam tylko, że jest używany przez Great Internet Mersenne Prime Research, i w moich paru testach spisywał się bardzo dobrze, złożoność: O(b × log b × log2 n), jako podstwa znowu pojawia się Małe Twierdzenie Fermata. To tyle, pozostała tylko notka o generowaniu liczb pierwszych, ale to już natępnym razem, do przeczytania! #Primes #Numerical #Python #python

Faktoryzacja Do Liczb Pierwszych

Jak już były testy(hashtag Primes), to teraz faktoryzacja, artykuł na Wikipedii szczegółowo opisuje dostępne metody. Wiele z nich (tych do dużych liczb) jest skomplikowana i raczej dla nas (jeśli nie pracujemy w kryptografii czy coś w tym stylu) mało użyteczna.

Ale w matematyce rekreacyjnej, jak adventofcode, hackerrank, projecteuler czy inne, wystarczy, w miarę szybko faktoryzować do, powiedzmy 10^16. A to można łatwo zrobić mając obliczoną tablicę liczb pierwszych do pierwiastka z n.

def factorize_trial(n, primes):
    """Factorizing n"""
    if miller_rabin(n):
        return n
    result = []
    for p in primes:
        while n % p == 0:
            result.append(p)
            n //= p
        if miller_rabin(n):
            result.append(n)
            break
    return result

primes można wygenerować używając, na przykład tego: simple_sieve.
Użyłem też, trochę zoptymalizowanego miller_rabin:

def miller_rabin(n):
    d = n - 1
    s = 0
    while d % 2 == 0:
        d >>= 1
        s += 1
    for repeat in range(20):
        a = 0
        while a == 0:
            a = random.randrange(n)
        if not miller_rabin_pass(a, s, d, n):
            return False
    return True
 
def miller_rabin_pass(a, s, d, n):
    a_to_power = pow(a, d, n)
    if a_to_power == 1:
        return True
    for i in range(s - 1):
        if a_to_power == n - 1:
            return True
        a_to_power = (a_to_power * a_to_power) % n
    return a_to_power == n - 1

Algorytm, jak widać iteruje po primes, próbując dzielić i dołączać do tablicy wynikowej, na końcu pętli jest sprawdzenie pierwszości, żeby ewentualnie zakończyć, gdy po podzieleniu n stanie się pierwsze.
Złożoność będzie primes(sqrt(n)) - liczba liczb pierwszych do pierwiastka z n, czyli będzie działał najwolniej, gdy liczba będzie mieć dwa duże czynniki pierwsze, ale dla wiekszości jest w miarę szybki. Kod. #Primes #Theory #Python #Numerical

Lucas - Lehmer Test

Żeby zakończyć przegląd efektywnych Prime Tests, część druga, część pierwsza dodam test Lucasa - Lehmera, sprawdza on tylko liczby pierwsze Mersenne'a - Zastosowania w kryptografii - jest szybszy niż Miller - Rabin. Artykuł na Wikipedii wyjaśnia dokładnie ideę i implementację. Dodam tylko kod w Pythonie:

def lucas_lehmer(p):
    s = 4
    m = exp(2, p) - 1
    for i in range(p - 2):
        s = ((s * s) - 2) % m
    return True if s == 0 else False

W sumie jest w tej samej klasie złożoności co Miller Rabin ale wykonuje mniej operacji. Program sprawdził 27 liczbę Mersenne'a w 79 sekund, gdzie Miller Rabin wyłączyłem po kilkunastu minutach.
Złożoność algorytmu O(p^2 log p log log p) - zakładając liniowy algorytm mnożenia (jak np. w GMP)

Czyli generalne program do sprawdzania dowolnych liczb: najlepszy wybór Miller - Rabin.
Do liczb Mersenne'a: Lucas - Lehmer.

Z probablistycznych jeszcze warto wspomnieć o teście Frobeniusa, jego jedna runda jest dłuższa, ale osiąga szybsze ograniczenie prawdopodobieństwa.
Są jeszcze algorytmy deterministyczne, jak na przykład AKS, ale jest niewydajny O((logn)^6).
Poza tym, AKS jest deterministyczny, ale w praktyce, jeśli Miller Rabin I AKS zwrócą różne wyniki na tej samej liczbie, to jest większa szansa, że to promieniowanie kosmiczne(!) przypadkiem zmmieniło bit i wynik w komputerze, na którym był zapuszczony AKS (gdyż liczył dłużej!). #Primes #Python #Theory #Numerical

Miller Rabin Test

Obiecany Miler Rabin, część pierwsza. Test Fermata, był prawie dobry, tylko dla pewnej klasy liczb (niewielkiej, ale jednak) zawsze się mylił (były złożone, ale przechodziły). Okazuje się, że można to usunąć, (Miller Rabin).

Najpierw Twierdzenie Fermata trochę inaczej zapisane:
Jeśli n jest liczbą pierwszą, a a dowolną liczbą dodatnią mniejszą od n, to a podniesione do potęgi n - 1przystaje do 1 modulo n.

Czyli(opis algorytmu):
Bierzemy losową liczbę 0 < a < n i podnosimy ją do potęgi n - 1 modulo n;
Podnosząc do potęgi, w każdym momencie podnoszenia do kwadratu szukamy "nietrywialnego pierwiastka kwadratowego jedynki modulo n", czyli sprawdzamy czy kolejna liczba, nie równa jeden lub n - 1 i podniesiona do kwadratu nie jest równa jeden modulo n (jeśli taką znajdziemy to liczba jest złożona). Dla liczby nieparzystej i złożonej, dla co najmniej połowy liczb a < n -1, sprawdzanie tym sposobem odkryje nietrywialny pierwiastek. Dlatego procedura Miller Rabin nie może być oszukana i można w granicy zredukowac błąd do zera gdy liczba prób dąży do nieskończoności. Pseudokod:

test_nontrivial(a, n):
    # t and u, t >=1, u odd and 2^tu = n - 1
    x[0] = modular-exponenation(a, u, n);
    for i -> 1 to t:
        x[i] = x[i - 1]^2 mod n;
        if x[i] == 1 and x[i - 1] != 1 x[i - 1] != n - 1:
            return True (composite)
        if x[t] != 1:
            return True
    return False

Dzięki sztuczce z dobraniem t i u, na początku i ustaleniu x[0], potem, aby podnieść a do n -1 modulo n, wystarczy podnieść x do kwadratu t razy, co umożliwia sprawdzanie warunku. Po iteracji, gdy nie mamy jedynki if x[t] != 1 to zwracamy True i finalnie False (nie znaleźliśmy nietrywialnych pierwiastków).
Teraz wystarczy tylko wykonać odpowiednia ilość testów w pętli, aby uzyskać zadaną dokładność, pseudokod:

miller-rabin(n, s):
    for j <- 1 to s:
        a = random(1, n - 1);
        if nontrivial_root(a, n):
            return False (composite)
        else:
            return True

I kod w Pythonie (nie wiele się różniący:)):

# 2. Miler - Rabin
 
# procedure nontrivial_root, which looking for a non trivial square root of one mod n
 
def nontrivial_root(a, n):
    """checking Fermat Theorem, and non trivial square root"""
 
    # find t and u, such that u odd, t >= 1 and n - 1 = 2^tu:
    t, u = 0, n - 1
    while u % 2 == 0:
        t += 1
        u //= 2
 
    x0 = modularexponenation(a, u, n)
    for i in range(1, t + 1):
        x1 = x0 ** 2 % n
        if x1 == 1 and x0 != 1 and x0 != n - 1:
            return True
    if x1 != 1:
        return True
    return False
 
def miller_rabin(n, s):
    """Miler Rabin Test"""
 
    # Return True if n = 2
    if n == 2:
        return True
    # Return False if even
    if n % 2 == 0:
        return False
 
    for i in range(s):
        a = randint(1, n - 1)
        if nontrivial_root(a, n):
            return False
    return True

Dokładność, można udowodnić, że błąd (gdy miller_rabin zwróci True) wynosi najwyżej 1 / 2^s, czyli, zgodnie z tą odpowiedzią na stacoverflow: https://stackoverflow.com/a/6330138, s = 40 wystarcza w zupełności. I na koniec złożoność obliczeniowa: O(k * (logn)^3) - jak daleko odeszliśmy od wykładniczej (co prawda w bitach:)). Kod na githubie. Mam nadzieję, że wywód był jasny, to tyle, dziękuję za cierpliwość. #Theory #Primes #Python #python #Numerical