source code of /small-scripts/demultiply.py

Last modified	2016-01-08
Lines	80

Parent directory Download CGIread sitemap Main page

Quick links: __init__ demultiply one test tester web

1. #!/usr/bin/python

3. import time

4. import random

5. import os

7. def demultiply(product, factor_a_min, factor_a_max, factor_b_min, factor_b_max):

8.     # Naive solution, brute force.

10.                                                 ## x = a * b

11.                                                 ## x in P, P in Z

12.                                                 ## a in Z

13.                                                 ## b in Z

15.     possibilities = []                          ## P

17.     # Loop over all possible values of a.

18.     factor_a = factor_a_min                     ## a

19.     while factor_a <= factor_a_max:

21.         if factor_a:

23.             factor_b = product//factor_a        ## b

24.             # Verify that both a and b are integers.

25.             if factor_a * factor_b == product:

27.                 if factor_b_min <= factor_b <= factor_b_max:

28.                     possibilities.append((factor_a, factor_b))

30.         factor_a += 1

32.     return possibilities

34. class tester():

35.     def __init__(self, factor_a_range, factor_b_range, samples):

36.         self.factor_a_min, self.factor_a_max = factor_a_range

37.         self.factor_b_min, self.factor_b_max = factor_b_range

38.         self.samples = samples

39.         self.times = []

40.         self.n_solutions = {}

42.     def one(self):

43.         a = random.randint(self.factor_a_min, self.factor_a_max)

44.         b = random.randint(self.factor_b_min, self.factor_b_max)

46.         T0 = time.time()

47.         P = demultiply(

48.             a * b,

49.             self.factor_a_min, self.factor_a_max,

50.             self.factor_b_min, self.factor_b_max

51.         )

52.         T1 = time.time()

54.         self.times.append(T1-T0)

56.         if len(P) in self.n_solutions:

57.             self.n_solutions[len(P)] += 1

58.         else:

59.             self.n_solutions[len(P)] = 1

61.     def test(self):

62.         self.times = []

63.         self.n_solutions = {}

65.         for i in range(self.samples):

66.             self.one()

70. def web():

71.     pass

74. if __name__ == '__main__':

76.     if os.getenv('QUERY_STRING'):

77.         web()

79.     t = tester((22000000, 23000000), (63000000, 64000000), 1000)