1#!/usr/bin/env python3
2# ^shebang: load the correct Python interpreter and environment.
3#============================================================================
4#
5# NAME
6#
7# PrimpolyRunningTimeAnalysis.py
8#
9# DESCRIPTION
10#
11# Primitive polynomial running time plots in Python using Sympy and Numpy.
12#
13# USAGE
14#
15# Better to run this from the Jupyter notebook:
16#
17# jupyter lab PrimpolyRunningTimeAnalysis.ipynb
18#
19# But you could also run it directly using Python:
20#
21# chmod +x PrimpolyRunningTimeAnalysis.py
22# ./PrimpolyRunningTimeAnalysis.py
23#
24# NOTES
25#
26# numpy: http://www.numpy.org
27# matplotlib https://matplotlib.org
28# Python interpreter: http://www.python.org
29# Python tutorial and reference: htttp://docs.python.org/lib/lib.html
30#
31# LEGAL
32#
33# Primpoly Version 16.4 - A Program for Computing Primitive Polynomials.
34# Copyright (C) 1999-2025 by Sean Erik O'Connor. All Rights Reserved.
35#
36# This program is free software: you can redistribute it and/or modify
37# it under the terms of the GNU General Public License as published by
38# the Free Software Foundation, either version 3 of the License, or
39# (at your option) any later version.
40#
41# This program is distributed in the hope that it will be useful,
42# but WITHOUT ANY WARRANTY; without even the implied warranty of
43# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
44# GNU General Public License for more details.
45#
46# You should have received a copy of the GNU General Public License
47# along with this program. If not, see <http://www.gnu.org/licenses/>.
48#
49# The author's address is seanerikoconnor!AT!gmail!DOT!com
50# with the !DOT! replaced by . and the !AT! replaced by @
51#
52#============================================================================
53
54import os # Path
55import sys # argc, argv, read/write I/O
56import platform # platform, uname
57import re # Regular expression support
58import math
59import numpy as np
60import pylab as py
61import subprocess
62import pickle # Python's own data file format.
63from deepdiff import DeepDiff # Deep difference for complicated data structures.
64
65def write_to_pickle_file( data, file_name ):
66 """Write data to a pickle file."""
67 try:
68 with open(file_name, 'wb') as f:
69 pickle.dump(data, f, pickle.HIGHEST_PROTOCOL)
70
71 if not os.path.exists( file_name ):
72 print( f"ERROR: Problem writing to {file_name} file doesn't exist." )
73 return None
74
75 except Exception as detail:
76 print( "ERROR: Problem writing to file {file_name} Caught RuntimeError exception; detail = {detail}")
77 return None
78
79
80def read_from_pickle_file( file_name ):
81 """Read data from a pickle file."""
82
83 if not os.path.exists( file_name ):
84 print( f"ERROR: {file_name} does not exist" )
85 return None
86 try:
87 with open( file_name, 'rb') as f:
88 data = pickle.load(f)
89 except Exception as detail:
90 print( "ERROR: Problem reading file {file_name} Caught RuntimeError exception; detail = {detail}")
91 return None
92
93 return data
94
95def data_differences( data1, data2 ):
96 """Return the differences between to dictionaries."""
97
98 changes = DeepDiff(data1, data2)
99 return changes
100
101
102def get_float_pattern():
103 """Generate a regular expression which matches floating point numbers.
104
105 Regular expressions format for Python is referenced here: https://docs.python.org/3/howto/regex.html
106
107 From [how to extract floating number from string](https://stackoverflow.com/questions/4703390/how-to-extract-a-floating-number-from-a-string)
108 Some people, when confronted with a problem, think 'I know, I'll use regular expressions.' Now they have two problems.
109 -Jamie Zawinski <jwz@netscape.com> wrote on Tue, 12 Aug 1997 13:16:22 -0700:
110 """
111
112 float_pattern = r"""
113 [-+]? # Optional sign: + or - or nothing
114 (?:
115 (?: \d* \. \d+) # .1 .12, 1.2 1.23
116 |
117 (?: \d+ \.?) # 1. 12. 1 12
118 )
119 (?: [Ee] [+-]? \d+ )? # Optional exponent: e1 e-2
120 """
121
122 return float_pattern
123
124
125def parse_primpoly_timing_output(line_of_file, **kwargs):
126 """
127 Parse the output of the command
128 time Primipoly p n
129 to get the running time.
130 """
131
132 real_time = None
133
134 # kwargs is a dictionary.
135 for key, value in kwargs.items():
136 if key in kwargs:
137 print( f"key = {key} value = {value}" )
138
139 debug = False
140 debug_value = kwargs.get("debug")
141 if debug_value is not None and debug_value is True:
142 debug = True
143
144 if line_of_file is None or len(line_of_file) == 0:
145 return None
146
147 #first_char = line_of_file[0]
148 # print("first char = ", first_char)
149
150 # Don't forget to backslash the vertical bar: \| since we want to match this char.
151 # Match all spaces with \s+ even those within a line.
152 # Tremendous speedup if we check the first char in the line before applying regular expressions.
153 #if first_char == 'X':
154 pattern1 = fr"""
155 real
156 \s+
157 (?P<real_time>
158 {get_float_pattern()}
159 )
160 """
161
162 pattern2 = fr"""
163 real
164 \s+
165 (?P<real_time>
166 {get_float_pattern()}
167 )
168 """
169 if debug:
170 print(f"pattern1 = {pattern1}")
171 print(f"pattern2 = {pattern2}")
172 print(f"line of file =\n|{line_of_file}|")
173
174 p1 = re.compile(pattern1, re.VERBOSE | re.IGNORECASE)
175 p2 = re.compile(pattern2, re.VERBOSE | re.IGNORECASE)
176
177 # Try both matches.
178 m1 = p1.search(line_of_file)
179 m2 = p2.search(line_of_file)
180
181 if m1:
182 real_time = float(m1.group('real_time'))
183 if debug:
184 print( "Match pattern 1. real_time = {real_time}")
185 elif m2:
186 real_time = float(m2.group('real_time'))
187 if debug:
188 print( "Match pattern 2. real_time = {real_time}")
189
190 return real_time
191
192
193def time_primpoly(**kwargs):
194
195 # kwargs is a dictionary.
196 for key, value in kwargs.items():
197 if key in kwargs:
198 print( f"key = {key} value = {value}" )
199
200 # Enable debugging?
201 debug = False
202 debug_value = kwargs.get("debug")
203 if debug_value is not None and debug_value is True:
204 debug = True
205
206 # All the degrees we wish to test.
207 degrees = [ 2, 10, 30, 50, 70, 90, 100, 120, 140, 145, 150, 160, 180, 200, 202, 210, 300, 400, 500, 550 ]
208 times = []
209
210 p = 2
211 for n in degrees:
212 # Run time Primpoly and collect the outputs.
213 print( f"Primpoly p = {p} n = {n}", file=sys.stderr )
214
215 standard_output = None
216 standard_error = None
217
218 # Set up the executable and the arguments for Linux. Try that first.
219 executableFileName="Bin/Primpoly.exe"
220 timeCommand="/usr/bin/time"
221 timeOptions = "-f 'real %e'" # %e is Wall clock time in seconds
222 completed_process=subprocess.run([timeCommand, timeOptions, executableFileName, str(p), str(n)], capture_output=True)
223 if completed_process.returncode == 0:
224 standard_output = completed_process.stdout.decode("utf-8")
225 standard_error = completed_process.stderr.decode("utf-8")
226 else:
227 if debug:
228 print("Could not run Linux version of time Primpoly. Running macOS version of time Primpoly")
229 # Didn't work? Set up the executable and the arguments for macOS. Try that next.
230 executableFile="Bin/Primpoly.exe"
231 timeCommand="time"
232 completed_process=subprocess.run([timeCommand, executableFileName, str(p), str(n)], capture_output=True)
233 if completed_process.returncode == 0:
234 standard_output = completed_process.stdout.decode("utf-8")
235 standard_error = completed_process.stderr.decode("utf-8")
236 # Still didn't work? Then abort.
237 else:
238 print( "ERROR: Could not run time command on the Primpoly executable. Did you build it with make? Aborting..." )
239 return None
240
241 if debug:
242 for line in standard_output.split('\n'):
243 print( f">>> {line}" )
244 for line in standard_error.split('\n'):
245 print( f"!!! {line}" )
246
247 # Parse the results to get the running time.
248 running_time_sec = parse_primpoly_timing_output(standard_error)
249 if running_time_sec is None:
250 print( "ERROR: Could not parse the running time. Aborting..." )
251 return None
252 else:
253 print( f"\trunning time = {running_time_sec}", file=sys.stderr )
254
255 times.append( running_time_sec )
256
257 return degrees, times
258
259
260def plot_running_times( file_name, **kwargs ):
261 """Plot the running times"""
262
263 debug = False
264 debug_value = kwargs.get("debug")
265 if debug_value is not None and debug_value is True:
266 debug = True
267
268 if (timing_data := read_from_pickle_file( file_name )) == None:
269 print( f"ERROR: No data in the running times file or no file {file_name}")
270 return
271 elif debug:
272 print( f"timing data (computer name, degrees and times = \n\t{timing_data}" )
273
274 try:
275 py.figure('Primpoly Running Time', figsize=(20,10))
276 py.title('Running Time vs Degree for Mod 2 Primitive Polynomials')
277 py.xlabel('Polynomial Degree')
278 py.ylabel('Running Time, Seconds')
279 py.semilogy()
280
281 legends = []
282 for computer_name, degrees_and_times in timing_data.items():
283 degrees, times = degrees_and_times
284 if debug:
285 print(f"degrees = {degrees}")
286 print(f"times = {times}")
287 print(f"name = {computer_name}")
288
289 py.plot( degrees, times )
290 legends.append( computer_name )
291
292 py.legend(legends)
293 py.show()
294 return
295 except Exception as err:
296 print( f"ERROR: Plotting went haywire for file {file_name}. Caught a general Exception {err}" )
297 return
298
299def compute_running_time_and_record(file_name):
300 """Time my primitive polynomial program and record the times."""
301
302 # Do we have any previously recorded timing data? If not, create an empty dictionary for it.
303 if (timing_data := read_from_pickle_file( file_name )) == None:
304 timing_data = {}
305
306 # Find out which type of computer system we are running on.
307 if platform.uname().system == 'Darwin' and platform.uname().machine == 'arm64' and platform.uname().processor == 'arm':
308 computer_name = "MacBook Pro 2021 Apple M1 Max macOS"
309 elif platform.uname().system == 'Linux' and platform.uname().machine == 'x86_64' and platform.uname().processor == 'x86_64':
310 computer_name = "CyberPowerPC Model C Series AMD Intel Ubuntu/Linux 22.04 LTS Jammy Jellyfish"
311 else:
312 computer_name = None
313 print( f"ERROR: unknown computer type" )
314 return
315
316 # Run the timing analysis.
317 degrees, times = time_primpoly()
318
319 if computer_name not in timing_data:
320 # If we don't yet have data for this computer, create a new dictionary entry.
321 timing_data[ computer_name ] = [degrees, times]
322 else:
323 # Else overwrite the old timing data.
324 timing_data[ computer_name ] = [degrees, times]
325
326 # Record to file.
327 write_to_pickle_file( timing_data, file_name )
328
329# timing_data_results = read_from_pickle_file( file_name )
330# diff = data_differences( timing_data, timing_data_results )
331# if diff is None or len(diff) == 0:
332# print( "no differences" )
333
334
335def update_running_times_and_plot_all():
336 """Read the running time from file and plot it"""
337
338 print( "Running Python Version {0:d}.{1:d}.{2:d}".format( sys.version_info[ 0 ], sys.version_info[ 1 ], sys.version_info[ 2 ] ) )
339
340 file_name = "primpoly_running_time.pickle"
341
342 # Compute running time on this system and record to file.
343 compute_running_time_and_record(file_name)
344
345 # Plot all running times so far recorded.
346 plot_running_times(file_name)
347
348if __name__ == '__main__':
349 """ If you run this as a standalone program:
350 chmod +x PrimpolyRunningTimeAnalysis.py
351 ./PrimpolyRunningTimeAnalysis.py
352 """
353
354 update_running_times_and_plot_all()
