هل يمكنني تقليل التعقيد الحسابي لهذا؟

Question

حسنا، لدي هذا القليل من التعليمات البرمجية التي تباطأ البرنامج بشكل كبير لأنها تعقيد خطي ولكنها تسمى الكثير من الأوقات مما يجعل التعقيد التربيعي البرنامجي. إذا كان ذلك ممكنا، أود أن أقليص تعقيدها الحسابي، لكن خلاف ذلك، سأحسن ذلك لأني أستطيع ذلك. حتى الآن لقد خفضت إلى:

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

      a += 1

أي شخص يرى أي شيء فاتنيه؟ شكرا!

تحرير: نسيت أن أذكر: n هو دائما رقم رئيسي.

تحرير 2: هنا هو برنامجي المحسن الجديد (شكرا لجميع المساهمات!):

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

تحرير 3: واختبارها في سياقها الحقيقي هو كثير أسرع! حسنا، يبدو أن هذا السؤال حل ولكن هناك العديد من الإجابات المفيدة. يجب أن أقول أيضا أنه وكذلك تلك الأمثل أعلاه، لقد قمت بتذكر الوظيفة باستخدام قواميس بيثون ...

Answer 1

بناء على تحرير 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

تجاهل الخوارزمية للحظة (نعم، وأنا أعلم، فكرة سيئة)، وقت التشغيل من هذا يمكن أن ينخفض باهظ فقط عن طريق التبديل من while ل for.

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

(نأمل أن يكون هذا خطأ خارج واحد. أنا عرضة لجعل هذه.)

شيء آخر أود أن أحاوله هو البحث إذا كان يمكن زيادة عرض الخطوة.

Answer 3

إلقاء نظرة على http://modular.fas.harvard.edu/ent/ent_py. وبعد وظيفة SQRTMOD تقوم بهذه المهمة إذا قمت بتعيين = -1 و P = n.

نقطة صغيرة تفتقدها هي أن وقت تشغيل الخوارزمية المحسنة الخاصة بك لا يزال في ترتيب الجذر التربيعي ل n. طالما لديك فقط الأعداد الأولية الصغيرة N (دعنا نقول أقل من 2 ^ 64) على ما يرام، وربما يجب أن تفضل تنفيذك إلى واحد أكثر تعقيدا.

إذا أصبحت Prime N أكبر، فقد تضطر إلى التبديل إلى خوارزمية باستخدام عدد قليل من نظرية الأرقام. إلى حد علمي، يمكن حل مشكلتك فقط مع خوارزمية الاحتمالية في سجل الوقت (N) ^ 3. إذا كنت أتذكر بشكل صحيح، فإن افتراض أن فرضية Riemann يحمل (التي يقوم بها معظم الأشخاص)، يمكن للمرء أن يظهر أن وقت تشغيل الخوارزمية التالية (في روبي - آسف، لا أعرف بيثون) هو سجل (سجل (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

الجزء البطيء يجد الآن رئيس الوزراء (الذي يأخذ تقريبا. سجل (n) ^ 4 عملية عدد صحيح)؛ العثور على الجذر التربيعي ل -1 يأخذ لعملي 512 بت لا يزال أقل من ثانية واحدة.

Answer 4

النظر في الحوسبة مسبقا النتائج وتخزينها في ملف. في الوقت الحاضر تحتوي العديد من المنصات على قدرة ضخمة على القرص. بعد ذلك، سيكون الحصول على النتيجة عملية س (1).

Answer 5

(بناء على إجابة آدم.) انظر إلى صفحة ويكيبيديا على المعاملة بالتبادل التربيعي:

X ^ 2 ≡ -1 (وزارة الدفاع P) هو قابلة للحل إذا وفقط إذا كانت P ≡ 1 (وزارة الدفاع 4).

ثم يمكنك تجنب البحث عن الجذر بدقة بالنسبة لأولئك Prime N غريبا غير متطابقين مع 1 Modulo 4:

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

Answer 6

يبدو أنك تحاول العثور على الجذر التربيعي من -1 modulo n. وبعد لسوء الحظ، هذه ليست مشكلة سهلة، اعتمادا على قيم n هي المدخلات في وظيفتك. اعتمادا علي n, ، قد لا يكون هناك حلا. يرى ويكيبيديا لمزيد من المعلومات حول هذه المشكلة.

Answer 7

تحرير 2: من المستغرب، تقليل القوى تقليل المربح يقلل من الوقت كثيرا، على الأقل في تثبيت Python2.5 الخاص بي. (أنا مندهش لأنني اعتقدت أن النفقات الفرعية لمتأخذ معظم الوقت، وهذا لا يقلل من عدد العمليات في الحلقة الداخلية.) يقلل من الوقت من 0.572 ثانية إلى 0.146s لجدول (1234577).

 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

نشر strager نفس الفكرة ولكن أعتقد أنه أقل ترميز بإحكام. تكرارا، إجابة إبريق هو الأفضل.

الإجابة الأصلية: قرص ترميز تافهة آخر على رأس كونراد رودولف:

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

يسرعها بشكل لاصق على جهاز الكمبيوتر المحمول الخاص بي. (حوالي 25٪ للجدول (1234577).)

يحرر: لم ألاحظ علامة Python3.0؛ لكن التغيير الرئيسي هو رفع جزء من الحساب من الحلقة، وليس استخدام xrange. وبعد (الأكاديمية لأن هناك خوارزمية أفضل.)

Answer 8

هل من الممكن لك أن تخزين النتائج؟

عندما تقوم بحساب كبير N، تعطيل النتائج لأسفل N تقريبا مجانا.

Answer 9

هناك شيء واحد تقوم به هو تكرار الحساب - * مرارا وتكرارا.

قم بإنشاء جدول للقيم مرة واحدة ثم ابحث عن الحلقة الرئيسية.

أيضا على الرغم من أن هذا ربما لا ينطبق عليك لأن اسم وظيفتك هو الجدول ولكن إذا استدعيت دالة تستغرق وقتا لحسابك يجب أن تخبئ النتيجة في الجدول، فما عليك سوى البحث عن جدول إذا قمت بالاتصال به مرة أخرى بنفس القيمة. هذا يوفر لك وقت حساب جميع القيم عند تشغيله لأول مرة ولكنك لا تضيع الوقت في تكرار الحساب أكثر من مرة.

Answer 10

مرت وإصلاح نسخة Harvard لجعلها تعمل مع Python 3. http://modular.fas.harvard.edu/ent/ent_py.

لقد قمت ببعض التغييرات الطفيفة لجعل النتائج تماما نفس وظيفة OP. هناك إجابات محتملة وأجبرت ذلك على إعادة الإجابة الأصغر.

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)

يستغرق هذا الإصدار حوالي 3ms لتشغيل حالات الاختبار أعلاه.

للمقارنة باستخدام الرقم الأول 1234577
OP Edit2 745ms.
الإجابة المقبولة 5222ms
وظيفة أعلاه 0.2ms