Puis-je réduire la complexité de calcul de cette situation?

Question

Eh bien, j'ai ce morceau de code qui ralentit le programme parce qu'il est extrêmement complexe linéaire, mais appelé beaucoup de temps rendant la complexité quadratique du programme. Si possible, je voudrais réduire la complexité de calcul, mais sinon je vais optimiser où je peux. Jusqu'à présent, je l'ai réduit à:

def table(n):
    a = 1
    while 2*a <= n:
      if (-a*a)%n == 1: return a

      a += 1

Quelqu'un voit tout ce que j'ai manqué? Merci!

EDIT: J'ai oublié de mentionner:. N est toujours un nombre premier

EDIT 2: Voici mon nouveau programme amélioré (merci de pour toutes les contributions!):

def table(n):
    if n == 2: return 1
    if n%4 != 1: return

    a1 = n-1
    for a in range(1, n//2+1):
        if (a*a)%n == a1: return a

EDIT 3: Et le tester dans son contexte réel, il est beaucoup plus vite! Eh bien cette question semble résolu mais il y a beaucoup de réponses utiles. Je dois aussi dire que, ainsi que ces optimisations ci-dessus, je memoized la fonction en utilisant des dictionnaires Python ...

Answer 1

D'après la deuxième édition de OP:

def table(n):
    if n == 2: return 1
    if n%4 != 1: return

    mod = 0
    a1 = n - 1
    for a in xrange(1, a1, 2):
        mod += a

        while mod >= n: mod -= n
        if mod == a1: return a//2 + 1

Answer 2

Ignorant l'algorithme pour un moment (oui, je sais, mauvaise idée), le temps d'exécution de ce qui peut être diminuée énormement juste en passant de while à for.

for a in range(1, n / 2 + 1)

(Espérons que cela ne dispose pas d'une erreur hors par un. Je suis enclin à les rendre.)

Une autre chose que je voudrais essayer est de regarder si la largeur de pas peut être augmentée.

Answer 3

Jetez un oeil à http://modular.fas.harvard.edu/ent/ent_py . La fonction sqrtmod fait le travail si vous définissez un = -1 et p = n.

Un petit point vous avez manqué est que le temps d'exécution de votre algorithme amélioré est encore dans l'ordre de la racine carrée de n. Tant que vous avez de petits nombres premiers n (disons moins de 2 ^ 64) qui est ok et vous devriez probablement préférer votre mise en œuvre à une plus complexe.

Si le premier n est plus grand, vous pourriez avoir à passer à un algorithme utilisant un peu de la théorie des nombres. À ma connaissance de votre problème peut être résolu que par un algorithme probabiliste dans le journal de temps (n) ^ 3. Si je me souviens bien, en supposant l'hypothèse de Riemann détient (que la plupart des gens), on peut montrer que le temps d'exécution de l'algorithme suivant (en Ruby - désolé, je ne sais pas python) est log (log (n)) * log (n) ^ 3:

class Integer
  # calculate b to the power of e modulo self
  def power(b, e)
    raise 'power only defined for integer base' unless b.is_a? Integer
    raise 'power only defined for integer exponent' unless e.is_a? Integer
    raise 'power is implemented only for positive exponent' if e < 0
    return 1 if e.zero?
    x = power(b, e>>1)
    x *= x
    (e & 1).zero? ? x % self : (x*b) % self
  end
  # Fermat test (probabilistic prime number test)
  def prime?(b = 2)
    raise "base must be at least 2 in prime?" if b < 2
    raise "base must be an integer in prime?" unless b.is_a? Integer
    power(b, self >> 1) == 1
  end
  # find square root of -1 modulo prime
  def sqrt_of_minus_one
    return 1 if self == 2
    return false if (self & 3) != 1
    raise 'sqrt_of_minus_one works only for primes' unless prime?
    # now just try all numbers (each succeeds with probability 1/2)
    2.upto(self) do |b|
      e = self >> 1
      e >>= 1 while (e & 1).zero?
      x = power(b, e)
      next if [1, self-1].include? x
      loop do
        y = (x*x) % self
        return x if y == self-1
        raise 'sqrt_of_minus_one works only for primes' if y == 1
        x = y
      end
    end
  end
end

# find a prime
p = loop do
      x = rand(1<<512)
      next if (x & 3) != 1
      break x if x.prime?
    end

puts "%x" % p
puts "%x" % p.sqrt_of_minus_one

La partie lente est de trouver maintenant le premier (., Qui dure environ log (n) ^ 4 opération entière); trouver la racine carrée de -1 prend pour des nombres premiers 512 bits encore moins d'une seconde.

Answer 4

Considérons pré-calcul des résultats et de les stocker dans un fichier. De nos jours, de nombreuses plates-formes ont une capacité énorme de disque. Ensuite, pour obtenir le résultat sera une opération O (1).

Answer 5

(bâtiment sur la réponse d'Adam.) Regardez la page Wikipedia sur réciprocité quadratique :

  

x ^ 2 ≡ -1 (mod p) est résoluble si et seulement si p ≡ 1 (mod 4).

Ensuite, vous pouvez éviter la recherche d'une racine précisément pour ceux de n premier impair qui ne sont pas en harmonie avec 1 modulo 4:

def table(n):
    if n == 2: return 1
    if n%4 != 1: return None   # or raise exception
    ...

Answer 6

On dirait que vous essayez de trouver la racine carrée de -1 modulo n. Malheureusement, ce n'est pas un problème facile, en fonction des valeurs de n sont entrés dans votre fonction. Selon n, il pourrait même ne pas être une solution. Voir Wikipedia pour plus d'informations sur ce problème.

Answer 7

Edit 2: De manière surprenante, réduisant la force la mise au carré réduit le temps beaucoup, au moins sur mon installation python2.5. (Je suis surpris parce que je pensais que les frais généraux d'interprète prenait la plupart du temps, et cela ne réduit pas le nombre d'opérations dans la boucle interne.) Réduit le temps de 0.572s à 0.146s de la table (1.234.577).

 def table(n):
     n1 = n - 1
     square = 0
     for delta in xrange(1, n, 2):
         square += delta
         if n <= square: square -= n
         if square == n1: return delta // 2 + 1

la même idée mais je penser moins fortement codée. Encore une fois, de réponse est la meilleure.

Réponse originale: Un autre tweak de codage trivial sur le dessus de Konrad Rudolph:

def table(n):
    n1 = n - 1
    for a in xrange(1, n // 2 + 1):
          if (a*a) % n == n1: return a

Accélère vers le haut sur mon ordinateur portable mesurablement. (Environ 25% de la table (1.234.577).)

Modifier Je n'ai pas remarqué la balise python3.0; mais la principale modification a été partie hissage du calcul de la boucle, pas l'utilisation de xrange. (Academic car il est un meilleur algorithme.)

Answer 8

Est-il possible pour vous de mettre en cache les résultats?

Lorsque vous calculez un grand n vous donne les résultats pour le bas n est presque gratuitement.

Answer 9

Une chose que vous faites est de répéter le calcul -a * a encore et encore.

Créer une table des valeurs une fois et ne pas regarder dans la boucle principale.

En outre, bien que cela ne concerne sans doute pas vous parce que votre nom de la fonction est la table mais si vous appelez une fonction qui prend le temps de vous calculer doit mettre en cache le résultat dans une table et juste faire une table regarder si vous l'appelez à nouveau avec la même valeur. Vous économiser le temps de calcul toutes les valeurs lors de la première manche, mais vous ne perdez pas de temps à répéter le calcul plus d'une fois.

Answer 10

Je suis passé par et fixé la version Harvard pour le faire fonctionner avec python 3.   http://modular.fas.harvard.edu/ent/ent_py

J'ai fait quelques modifications pour rendre les résultats exactement la même que la fonction de l'OP. Il y a deux réponses possibles et je l'ai forcé à retourner la plus petite réponse.

import timeit

def table(n):

    if n == 2: return 1
    if n%4 != 1: return

    a1=n-1

    def inversemod(a, p):
        x, y = xgcd(a, p)
        return x%p

    def xgcd(a, b):
        x_sign = 1
        if a < 0: a = -a; x_sign = -1
        x = 1; y = 0; r = 0; s = 1
        while b != 0:
            (c, q) = (a%b, a//b)
            (a, b, r, s, x, y) = (b, c, x-q*r, y-q*s, r, s)
        return (x*x_sign, y)

    def mul(x, y):      
        return ((x[0]*y[0]+a1*y[1]*x[1])%n,(x[0]*y[1]+x[1]*y[0])%n)

    def pow(x, nn):      
        ans = (1,0)
        xpow = x
        while nn != 0:
           if nn%2 != 0:
               ans = mul(ans, xpow)
           xpow = mul(xpow, xpow)
           nn >>= 1
        return ans

    for z in range(2,n) :
        u, v = pow((1,z), a1//2)
        if v != 0:
            vinv = inversemod(v, n)
            if (vinv*vinv)%n == a1:
                vinv %= n
                if vinv <= n//2:
                    return vinv
                else:
                    return n-vinv


tt=0
pri = [ 5,13,17,29,37,41,53,61,73,89,97,1234577,5915587277,3267000013,3628273133,2860486313,5463458053,3367900313 ]
for x in pri:
    t=timeit.Timer('q=table('+str(x)+')','from __main__ import table')
    tt +=t.timeit(number=100)
    print("table(",x,")=",table(x))

print('total time=',tt/100)

Cette version prend environ 3 ms pour exécuter dans les cas de test ci-dessus.

À titre de comparaison en utilisant le nombre premier 1234577
OP Edit2 745ms
Les 522ms de réponse acceptée
Les 0,2ms de la fonction ci-dessus