Fattori di un numero intero

bb3OK, sono indaffarato su altre cose ma non posso abbandonare Racket, il mio linguaggio di programmazione preferito (con zilioni di altri, tutti pari-merito).
E come già in passato (è piaciuto) un confronto con altri dei miei linguaggi preferiti. Poi prossimamente continua lo studio di Rust, anche lì si stanno accumulando robe: sono travolto dai ritardi 🙄

Sto copiando da Rosetta code, qui: Factors of an integer.

AWK

Comincio con un’eccezione: AWK non è multipiattaforma ma ci sono affezionato da sempre

#!/usr/bin/awk
BEGIN {
    print("enter a number or C/R to exit")
}
{   if ($0 == "") { exit(0) }
    if ($0 !~ /^[0-9]+$/) {
      printf("invalid: %s\n",$0)
      next
    }
    n = $0
    printf("factors of %s:",n)
    for (i=1; i<=n; i++) {
      if (n % i == 0) {
        printf(" %d",i)
      }
    }
    printf("\n")
}

f0Per passare il numero da fattorizzare sulla riga di comando si può fare:

#!/usr/bin/awk
{
    if ($0 == "") { exit(0) }
    if ($0 !~ /^[0-9]+$/) {
      printf("invalid: %s\n",$0)
      next
    }
    n = $0
    printf("factors of %s:",n)
    for (i=1; i<=n; i++) {
      if (n % i == 0) {
        printf(" %d",i)
      }
    }
    printf("\n")
}

f1E il comando si può –ovviamente semplificare:

#!/bin/bash
echo $1 | awk -f f1.awk

f2

Python

La versione più semplice è semplicissima:

#!/usr/bin/python3

def factors(n):
    return [i for i in range(1, n + 1) if not n%i]

print(42, ":", factors(42))
print(2701, ":", factors(2701))
print(32768, ":", factors(32767))

f3La prima ottimizzazione si ottiene considerando solo i numeri compresi nell’intervallo [1 .. n/2 + 1]. Notare // per la divisione fra interi (dalla versione 3). In questo caso il numero stesso non compare nell’output.

#!/usr/bin/python3

def factors(n):
    return [i for i in range(1, n // 2 + 1) if not n%i]

print(42, ":", factors(42))
print(2701, ":", factors(2701))
print(32768, ":", factors(32767))

f4Meglio ancora, i divisori non possono essere maggiori della radice quadrata del numero; output come il caso precedente (ho modificato il range del for facendolo partire da 2, con 1 il numero testato compare nell’output).

#!/usr/bin/python3

from math import sqrt

def factors(n):
    factors = set()
    for x in range(2, int(sqrt(n)) + 1):
        if n % x == 0:
            factors.add(x)
            factors.add(n // x)
    return sorted(factors)
      
print(42, ":", factors(42))
print(2701, ":", factors(2701))
print(32768, ":", factors(32767))

Quant’è efficace l’ottimizzazione? considero un numero grosso, 1323116819 e provo, modificando gli script che elaborino il primo parametro passato, così:

#!/usr/bin/python3

import sys

def factors(n):
    return [i for i in range(1, n + 1) if not n%i]

N = int(sys.argv[1])
print(N, ":", factors(N))

f5Eh, sì 😀

Racket

La versione elementare:

#lang racket
 
;; a naive version
(define (naive-factors n)
  (for/list ([i (in-range 1 (add1 n))]
             #:when (zero? (modulo n i))) i))

(printf "~a : " 42)
(printf "~a \n" (naive-factors 42))

f6Molto meglio usando factorize per ricavare i primi e costruirne la lista:

#lang racket
 
(require math)
(define (factors n)
  (sort (for/fold ([l '(1)]) ([p (factorize n)])
          (append (for*/list ([e (in-range 1 (add1 (cadr p)))] [x l])
                    (* x (expt (car p) e)))
                  l))
        <))

(printf "~a : " 42)
(printf "~a \n" (factors 42))

 

Quanto è più veloce? Provo con lo stesso numero usato per Python:

#lang racket

;; a naive version
(define (naive-factors n)
  (for/list ([i (in-range 1 (add1 n))]
             #:when (zero? (modulo n i))) i))

(require math)
(define (factors n)
  (sort (for/fold ([l '(1)]) ([p (factorize n)])
          (append (for*/list ([e (in-range 1 (add1 (cadr p)))] [x l])
                    (* x (expt (car p) e)))
                  l))
        <))

(define N 1323116819)
(printf "naive version, ~a : " N)
(time (printf "~a \n" (naive-factors N)))
(printf "better version, ~a : " N)
(time (printf "~a \n" (factors N)))

f7Ma esiste un modo ancora migliore, usare la funzione divisors che fa la stessa cosa di factorize ma è più veloce. Uso il numero enorme di Rosetta.

f8

Anche sulle cose semplici c’è molto da imparare 🙄

:mrgreen:

Posta un commento o usa questo indirizzo per il trackback.

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo di WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione /  Modifica )

Google photo

Stai commentando usando il tuo account Google. Chiudi sessione /  Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione /  Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione /  Modifica )

Connessione a %s...

Questo sito utilizza Akismet per ridurre lo spam. Scopri come vengono elaborati i dati derivati dai commenti.

%d blogger hanno fatto clic su Mi Piace per questo: