Talk:Primorial numbers: Difference between revisions
No edit summary |
|||
(11 intermediate revisions by 4 users not shown) | |||
Line 3:
say "First ten primorials: ", join ", ", map { pn_primorial($_) } 0..9;</lang> and all is done ;-)
[[user#Horsth|Horsth]]
: I just added a version using the new vecprod command. It is quite a bit faster. It uses a product tree for efficient large vector products -- the old comment was misleading about using a factor tree. [[User:Danaj|Danaj]] ([[User talk:Danaj|talk]]) 16:50, 9 October 2018 (UTC)
::Once I figured out what a "product tree" is, simply multiplying in pairs (technically adjacent, not that my Phix entry does that) I was positively ''shocked'' to see a better than 50-fold performance improvement (6 mins => 6 secs). --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|talk]]) 04:28, 22 March 2020 (UTC)
== a faster-than-exponential growth rate in CPU time stated by dinosaur ==
===Story===
school - multiplication ist quadratic in runtime O(count of digits) ~ (count of digits)^2
<pre>Prime(100000) = 1299709, Primorial(100000) ~ 0.1909604E+563921 121.547 seconds.
Line 18 ⟶ 20:
121,547*(1.17*1.03*10)^2 s = 17651 s [[user#Horsth|Horsth]]
The implementation of primorial I am using, running on this laptop, took 0.002909 seconds for primorial 100000 and 0.049093 seconds for primorial 1000000. With digit counts, that became 0.004267 seconds and 0.04369 seconds. I guess that's faster than exponential growth rate if by fast you mean the execution time... but ... actually, I'm not sure where I'm going with this. I am mildly surprised that digit count could be faster than the raw primorial but that might just be random variation --[[User:Rdm|Rdm]] ([[User talk:Rdm|talk]]) 20:41, 8 April 2016 (UTC) Edit: System Info claims I'm working with an i7: 2.8GHz clock, 256KB L2, 6MB L3 - no mention of L1. --[[User:Rdm|Rdm]] ([[User talk:Rdm|talk]]) 09:26, 9 April 2016 (UTC)
:According to System Info, the computer has 64KB of L1 I-cache, 16KB L1 D-cache, and 2048KB of L2 cache, with further jargon about 2 way set associative, 64 byte line size, etc. and no mention of L3. Later, I see that the GIMP calculation gives 8MB for L3 on this AMD k10. However, I have no idea how much of each resource is devoted to the various activities such as running the GIMP crunch and windows itself. This is why experimental timings are tricky to perform as well as being a load on the patience. I am however surprised by the speeds quoted by some contributors, given that towards the end the number has millions of digits.
:As for the standard multiplication procedure of n digits by m digits consuming time proportional to n.m, remember that my version cheats by using a one digit multiplicand (err, the second number in a*b) even though it is much larger than the base of arithmetic. Computer crunching of integers is unaffected by whether x is multiplied by 12 or 1234567, except for overflows. Thus, its running time should be proportional to n, the number of digits in the big number. In principle, and ignoring caches. If successive primorials were attained by multiplying by a constant, then that number of digits would increase linearly, but of course the multiplicand is increasing in size itself. If that increase was the same as with factorials then the number of digits would increase according to log(x!) which is proportional to x*log(x) via Stirling's approximation, which is to say a linear growth (the x) multiplied by a factor that grows ever more slowly (the log(x))
:But Primorial(x) grows even faster than x! However, I didn't look and think long about the cpu timings before making the remark about "faster than exponential". I shall twiddle the prog. to produce more reports on timing... [[User:Dinosaur|Dinosaur]] ([[User talk:Dinosaur|talk]]) 08:51, 9 April 2016 (UTC)
:: On reading http://rosettacode.org/mw/index.php?title=Primorial_numbers&type=revision&diff=225184&oldid=225110 I think I'm beginning to understand your point of view. I guess the issue is "in proportion to what?" For example, if we consider resource consumption (quite a lot) in proportion to the number of arguments (always just one), resource growth is infinite. If we think of resource growth in proportion to the number of digits in the argument we get "resource consumption (time to complete) growth faster than exponential". If we think of resource growth in proportion to the numerical value of the argument time consumed growth grows faster than linear.
:: Anyways, I guess a general issue here is that we tend to think in "shorthand" and when relating those thought to other people it often takes some extra work to make sure they understand our thinking. --[[User:Rdm|Rdm]] ([[User talk:Rdm|talk]]) 01:58, 10 April 2016 (UTC)
:Our edits clashed! In the article I have rephrased the usage of "exponential" to note that it is the task that is growing exponentially (n = 10^i for i = 1, 2, 3, ...) so that even for a linear exercise, the work would grow exponentially. But here there is a further growth factor beyond the linear, because the number size is growing faster than linear, because n is growing... The supposition being that a multiply is linear in (number of digits) given that the multiplicand is one (embolismic) digit only. Except, we know that sooner or later, its digit count will grow. The unit of "sizeness" is not always obvious or convenient. To calculate Primorial(n) the task size is obviously determined by the value of n, from which is deduced log(n) for the number of digits both of n itself and Primorial(n) and one argues about the time for a multiply with those sizes of digit strings, and then perhaps the integration of those times so as to reach n from 1. All of which depends on n. But, since digit string length is so important, one might choose to talk about log(n) as being the unit of size. In the factoring of numbers, for example, I (and Prof. Knuth) speak of n and sqrt(n), but, with ever larger n, it seems now it is fashionable to use log(n) as the unit, and speak of "polynomial time in N" or similar, when N is actually log(n)
:Righto, another overnight run, this time with a report every thousand for n, d, and t where t is the cpu time to attain n after reaching n - 1000. So, from 99000 to attain 100000 the digit count went from 557809 to 563921 and the cpu time was 2·625. For 999000 to 1000000 the digit count went from 6715619 to 6722809 and the cpu time was 33·969. Plotting showed almost linear growth rates ''across this limited span'':
Correlation
0·99990 t = d*5·636E-6 -0·41458
0·99973 d = n*6·6983 -125797·8
0·99943 t = n*3·7744E-5 - 1·1205
:These were for data only up to n = 800,000 because there was a change in slope subsequently, probably because I stopped using the computer for other minor activity and thus didn't disrupt its various buffers. The Mersenne prime calculations continued. The points wobble above and below the fitted line across the span, and there is a bend visible at the start where the overall line is too low. That is, at the start the calculation is going a little faster and presumably, one could talk about not yet overflowing some on-chip memory buffer as another reason for non-linearity. Similarly, at the high end the points start to rise above the fitted line, and one could talk about a growth factor such as log(n) rather than a constant. This is obscured by the greater speed later on when I had walked away from the toiling computer. Nevertheless, one can see that a slight curve is being approximated by a straight line over a limited span, which means that using the start to attempt to identify the effect of a cpu buffer size will be tricky. Even so, a log(n) vs. log(t) plot shows a change of slope at the start - except that is for only the first few points. Alas, with "only" a few thousand digits to the big number, the resolution of the CPU timing function is insufficient to show finer details, and repeating the calculation a hundred times (say) will require auxiliary storage to enable the repetition and this will change the workings of the presumed buffering processes away from what was intended to be investigated. A frustrating business.
:Unfortunately, there is no provision for posting images, and anyway I've had a lot of trouble with Octave producing damaged plot files (.svg, .png, etc.) having to resort to screen image captures, so instead, here are the data:
:: You should be able to post images now. Look for an "Upload File" link at the bottom of the page. Also, you might want to look at where the time is going in your implementation - I am going to guess that it's in your code to generate the prime numbers. --[[User:Rdm|Rdm]] ([[User talk:Rdm|talk]]) 03:00, 10 April 2016 (UTC)
:::Pox! I have just created file Primorial.cpuTime.svg, but, "Error creating thumbnail: /bin/bash: rsvg-convert: command not found" results. Inkscape however draws the plot without difficulty, though at 657KB the file is a bit large for just a thousand points, a line, and some annotation. And now that it is uploaded, I can't see how to delete it. I shall attempt to replace it by a screen capture. As for Octave, it won't "Print" the plot as either a .png nor a .jpg due to some complaint of its own "'C:\Program' is not recognized as an internal or external command, operable program or batch file." so a tar pit there.
:::The calculation of the primes is not a problem, because all million are prepared in array PRIME before any Primorial attempts are made, and the time for this is somewhere in the blink of starting the run and the first Primorial results appearing even as the screen window manifests. [[User:Dinosaur|Dinosaur]] ([[User talk:Dinosaur|talk]]) 06:30, 10 April 2016 (UTC)
::::And I can't replace the .svg file by a .jpg because I can't change the name of the file. So, a new file (only 38KB in this format), and damnit, I forgot to give the name the prefix "Primorial.cpu" [[File:Time.jpg]]
And here is a plot of cpu time against the number of digits in the big number, which is successively being multiplied by a ''single'' digit value. [[File:Primorial.CPUtime.digits.jpg]]
:::::Only admins are allowed to delete files. I've removed "Primorial.cpuTime.svg". --[[User:AndiPersti|Andreas Perstinger]] ([[User talk:AndiPersti|talk]]) 18:36, 10 April 2016 (UTC)
===Grist===
<pre>
1000, 3393, 0.000
2000, 7483, 0.016
3000, 11829, 0.047
4000, 16340, 0.047
5000, 20975, 0.078
6000, 25706, 0.094
7000, 30519, 0.109
8000, 35400, 0.141
9000, 40342, 0.156
10000, 45337, 0.172
11000, 50381, 0.219
12000, 55468, 0.203
13000, 60595, 0.250
14000, 65759, 0.266
15000, 70957, 0.250
16000, 76187, 0.328
17000, 81447, 0.344
18000, 86735, 0.359
19000, 92050, 0.391
20000, 97389, 0.406
21000, 102753, 0.422
22000, 108139, 0.469
23000, 113547, 0.484
24000, 118975, 0.500
25000, 124424, 0.531
26000, 129891, 0.562
27000, 135377, 0.578
28000, 140881, 0.609
29000, 146401, 0.625
30000, 151937, 0.656
31000, 157490, 0.703
32000, 163057, 0.688
33000, 168640, 0.750
34000, 174237, 0.766
35000, 179849, 0.750
36000, 185473, 0.797
37000, 191111, 0.812
38000, 196762, 0.859
39000, 202425, 0.891
40000, 208100, 0.906
41000, 213787, 0.938
42000, 219486, 0.953
43000, 225196, 1.000
44000, 230916, 1.016
45000, 236648, 1.047
46000, 242390, 1.062
47000, 248143, 1.094
48000, 253905, 1.156
49000, 259678, 1.156
50000, 265460, 1.156
51000, 271251, 1.203
52000, 277052, 1.234
53000, 282862, 1.234
54000, 288681, 1.297
55000, 294508, 1.297
56000, 300345, 1.328
57000, 306189, 1.359
58000, 312042, 1.406
59000, 317903, 1.422
60000, 323772, 1.453
61000, 329649, 1.484
62000, 335534, 1.516
63000, 341426, 1.531
64000, 347326, 1.562
65000, 353233, 1.594
66000, 359148, 1.609
67000, 365069, 1.641
68000, 370998, 1.688
69000, 376933, 1.719
70000, 382876, 1.719
71000, 388825, 1.719
72000, 394780, 1.766
73000, 400743, 1.812
74000, 406711, 1.844
75000, 412686, 1.875
76000, 418668, 1.922
77000, 424656, 1.938
78000, 430649, 1.938
79000, 436649, 1.969
80000, 442655, 2.016
81000, 448667, 2.047
82000, 454684, 2.062
83000, 460708, 2.109
84000, 466737, 2.141
85000, 472772, 2.156
86000, 478812, 2.281
87000, 484857, 2.234
88000, 490908, 2.281
89000, 496965, 2.297
90000, 503026, 2.328
91000, 509093, 2.359
92000, 515165, 2.391
93000, 521242, 2.422
94000, 527324, 2.438
95000, 533411, 2.500
96000, 539504, 2.516
97000, 545601, 2.547
98000, 551703, 2.578
99000, 557809, 2.594
100000, 563921, 2.625
101000, 570037, 2.656
102000, 576158, 2.672
103000, 582283, 2.719
104000, 588413, 2.750
105000, 594548, 2.797
106000, 600687, 2.812
107000, 606831, 2.859
108000, 612978, 2.891
109000, 619131, 2.922
110000, 625287, 2.969
111000, 631448, 2.984
112000, 637613, 3.047
113000, 643782, 3.094
114000, 649956, 3.094
115000, 656133, 3.156
116000, 662315, 3.156
117000, 668500, 3.203
118000, 674690, 3.281
119000, 680884, 3.297
120000, 687081, 3.344
121000, 693283, 3.359
122000, 699488, 3.422
123000, 705698, 3.453
124000, 711911, 3.500
125000, 718128, 3.516
126000, 724349, 3.547
127000, 730573, 3.625
128000, 736801, 3.672
129000, 743033, 3.703
130000, 749268, 3.734
131000, 755507, 3.797
132000, 761750, 3.828
133000, 767996, 3.875
134000, 774246, 3.922
135000, 780499, 3.953
136000, 786756, 3.984
137000, 793016, 4.047
138000, 799280, 4.062
139000, 805547, 4.141
140000, 811817, 4.172
141000, 818091, 4.188
142000, 824368, 4.250
143000, 830648, 4.281
144000, 836932, 4.312
145000, 843219, 4.375
146000, 849509, 4.391
147000, 855802, 4.422
148000, 862099, 4.438
149000, 868398, 4.500
150000, 874701, 4.547
151000, 881007, 4.578
152000, 887316, 4.641
153000, 893628, 4.688
154000, 899943, 4.688
155000, 906261, 4.750
156000, 912583, 4.766
157000, 918907, 4.781
158000, 925234, 4.859
159000, 931564, 4.875
160000, 937898, 4.922
161000, 944234, 4.984
162000, 950573, 4.984
163000, 956915, 5.016
164000, 963259, 5.078
165000, 969607, 5.094
166000, 975958, 5.109
167000, 982311, 5.188
168000, 988667, 5.203
169000, 995026, 5.156
170000,1001388, 5.219
171000,1007752, 5.312
172000,1014119, 5.328
173000,1020489, 5.375
174000,1026862, 5.391
175000,1033238, 5.484
176000,1039616, 5.500
177000,1045997, 5.484
178000,1052380, 5.562
179000,1058766, 5.594
180000,1065155, 5.656
181000,1071546, 5.656
182000,1077940, 5.703
183000,1084336, 5.688
184000,1090735, 5.750
185000,1097137, 5.812
186000,1103541, 5.875
187000,1109948, 5.906
188000,1116357, 5.922
189000,1122768, 5.891
190000,1129182, 6.000
191000,1135599, 6.016
192000,1142018, 6.047
193000,1148439, 6.109
194000,1154863, 6.094
195000,1161290, 6.172
196000,1167718, 6.188
197000,1174149, 6.250
198000,1180583, 6.250
199000,1187018, 6.297
200000,1193457, 6.344
201000,1199897, 6.359
202000,1206340, 6.406
203000,1212785, 6.438
204000,1219233, 6.469
205000,1225682, 6.516
206000,1232134, 6.547
207000,1238588, 6.578
208000,1245045, 6.609
209000,1251504, 6.609
210000,1257965, 6.703
211000,1264428, 6.750
212000,1270893, 6.734
213000,1277361, 6.828
214000,1283831, 6.859
215000,1290303, 6.859
216000,1296777, 6.938
217000,1303254, 6.953
218000,1309732, 7.000
219000,1316213, 7.047
220000,1322696, 7.047
221000,1329181, 7.141
222000,1335668, 7.125
223000,1342158, 7.188
224000,1348649, 7.203
225000,1355143, 7.281
226000,1361638, 7.266
227000,1368136, 7.328
228000,1374635, 7.344
229000,1381137, 7.406
230000,1387641, 7.406
231000,1394147, 7.484
232000,1400654, 7.516
233000,1407164, 7.531
234000,1413676, 7.594
235000,1420189, 7.609
236000,1426705, 7.609
237000,1433223, 7.703
238000,1439742, 7.719
239000,1446264, 7.734
240000,1452788, 7.812
241000,1459313, 7.828
242000,1465841, 7.891
243000,1472370, 7.938
244000,1478902, 7.875
245000,1485435, 7.938
246000,1491970, 8.031
247000,1498507, 8.078
248000,1505046, 8.094
249000,1511587, 8.094
250000,1518130, 8.203
251000,1524675, 8.219
252000,1531221, 8.250
253000,1537770, 8.266
254000,1544320, 8.328
255000,1550873, 8.344
256000,1557427, 8.391
257000,1563983, 8.422
258000,1570540, 8.484
259000,1577100, 8.500
260000,1583661, 8.531
261000,1590224, 8.562
262000,1596789, 8.609
263000,1603355, 8.656
264000,1609924, 8.672
265000,1616494, 8.719
266000,1623066, 8.672
267000,1629640, 8.750
268000,1636215, 8.812
269000,1642792, 8.875
270000,1649371, 8.859
271000,1655952, 8.906
272000,1662534, 8.984
273000,1669118, 9.031
274000,1675704, 9.047
275000,1682291, 9.109
276000,1688881, 9.109
277000,1695472, 9.141
278000,1702064, 9.188
279000,1708658, 9.250
280000,1715254, 9.297
281000,1721852, 9.297
282000,1728451, 9.312
283000,1735052, 9.375
284000,1741655, 9.406
285000,1748259, 9.391
286000,1754865, 9.516
287000,1761472, 9.516
288000,1768082, 9.578
289000,1774692, 9.594
290000,1781305, 9.625
291000,1787919, 9.703
292000,1794534, 9.734
293000,1801151, 9.750
294000,1807770, 9.781
295000,1814391, 9.828
296000,1821013, 9.859
297000,1827636, 9.844
298000,1834261, 9.906
299000,1840888, 9.938
300000,1847516, 9.953
301000,1854146, 9.969
302000,1860777,10.047
303000,1867410,10.094
304000,1874045,10.109
305000,1880681,10.203
306000,1887318,10.047
307000,1893958,10.250
308000,1900598,10.281
309000,1907240,10.250
310000,1913884,10.328
311000,1920529,10.422
312000,1927176,10.438
313000,1933824,10.500
314000,1940474,10.547
315000,1947125,10.516
316000,1953777,10.359
317000,1960431,10.547
318000,1967087,10.578
319000,1973744,10.719
320000,1980402,10.688
321000,1987062,10.781
322000,1993724,10.719
323000,2000387,10.828
324000,2007051,10.875
325000,2013717,10.594
326000,2020384,10.859
327000,2027052,11.016
328000,2033722,11.062
329000,2040394,11.031
330000,2047067,11.156
331000,2053741,11.078
332000,2060417,11.125
333000,2067094,11.188
334000,2073772,11.297
335000,2080452,11.297
336000,2087133,11.344
337000,2093816,11.297
338000,2100500,11.359
339000,2107186,11.391
340000,2113873,11.453
341000,2120561,11.516
342000,2127250,11.562
343000,2133941,11.438
344000,2140633,11.625
345000,2147327,11.609
346000,2154022,11.656
347000,2160718,11.688
348000,2167416,11.641
349000,2174115,11.781
350000,2180815,11.859
351000,2187517,11.812
352000,2194220,11.938
353000,2200924,11.953
354000,2207630,11.984
355000,2214337,12.062
356000,2221045,12.078
357000,2227755,12.109
358000,2234466,11.953
359000,2241178,12.172
360000,2247891,12.141
361000,2254606,12.219
362000,2261322,12.344
363000,2268040,12.156
364000,2274758,12.281
365000,2281478,12.375
366000,2288199,12.406
367000,2294922,12.250
368000,2301646,12.484
369000,2308371,12.500
370000,2315097,12.641
371000,2321825,12.484
372000,2328553,12.453
373000,2335283,12.766
374000,2342015,12.734
375000,2348747,12.750
376000,2355481,12.844
377000,2362216,12.812
378000,2368952,12.750
379000,2375690,12.859
380000,2382429,12.875
381000,2389169,12.906
382000,2395910,13.031
383000,2402652,13.031
384000,2409396,13.094
385000,2416141,13.125
386000,2422887,13.250
387000,2429635,13.250
388000,2436383,13.219
389000,2443133,13.312
390000,2449884,13.312
391000,2456636,13.203
392000,2463389,13.469
393000,2470144,13.344
394000,2476900,13.453
395000,2483657,13.547
396000,2490415,13.594
397000,2497174,13.609
398000,2503935,13.641
399000,2510696,13.672
400000,2517459,13.781
401000,2524223,13.766
402000,2530988,13.859
403000,2537755,13.828
404000,2544522,13.812
405000,2551291,13.797
406000,2558061,13.906
407000,2564832,13.812
408000,2571604,14.000
409000,2578377,14.047
410000,2585151,14.016
411000,2591927,14.125
412000,2598703,14.094
413000,2605481,14.125
414000,2612260,14.234
415000,2619040,14.250
416000,2625821,14.266
417000,2632603,14.375
418000,2639387,14.312
419000,2646171,14.375
420000,2652957,14.500
421000,2659743,14.484
422000,2666531,14.438
423000,2673320,14.578
424000,2680110,14.531
425000,2686901,14.578
426000,2693694,14.641
427000,2700487,14.719
428000,2707281,14.781
429000,2714077,14.750
430000,2720873,14.812
431000,2727671,14.844
432000,2734470,14.766
433000,2741270,14.906
434000,2748071,14.969
435000,2754873,14.969
436000,2761676,14.938
437000,2768480,14.984
438000,2775285,15.000
439000,2782091,15.266
440000,2788899,15.219
441000,2795707,15.359
442000,2802516,15.312
443000,2809327,15.375
444000,2816139,15.406
445000,2822951,15.422
446000,2829765,15.484
447000,2836580,15.562
448000,2843395,15.625
449000,2850212,15.656
450000,2857030,15.672
451000,2863849,15.766
452000,2870669,15.672
453000,2877490,15.781
454000,2884312,15.750
455000,2891135,15.859
456000,2897959,15.906
457000,2904784,15.797
458000,2911610,15.594
459000,2918437,15.547
460000,2925265,15.609
461000,2932094,15.891
462000,2938924,16.109
463000,2945755,16.094
464000,2952587,16.172
465000,2959420,16.172
466000,2966255,16.297
467000,2973090,16.281
468000,2979926,16.203
469000,2986763,16.328
470000,2993601,16.375
471000,3000440,16.422
472000,3007280,16.484
473000,3014121,16.516
474000,3020963,16.578
475000,3027806,16.641
476000,3034650,16.594
477000,3041495,16.547
478000,3048341,16.703
479000,3055188,16.688
480000,3062036,16.797
481000,3068885,16.812
482000,3075734,16.750
483000,3082585,16.828
484000,3089437,16.922
485000,3096290,16.875
486000,3103143,16.969
487000,3109998,17.047
488000,3116853,17.031
489000,3123710,17.031
490000,3130568,17.172
491000,3137426,17.141
492000,3144285,17.188
493000,3151146,17.297
494000,3158007,17.344
495000,3164869,17.375
496000,3171732,17.359
497000,3178597,17.453
498000,3185462,17.453
499000,3192328,17.469
500000,3199195,17.562
501000,3206062,17.547
502000,3212931,17.562
503000,3219801,17.781
504000,3226672,17.812
505000,3233543,17.797
506000,3240416,17.766
507000,3247289,17.844
508000,3254163,17.938
509000,3261039,17.969
510000,3267915,17.969
511000,3274792,18.078
512000,3281670,18.062
513000,3288549,18.062
514000,3295429,18.078
515000,3302310,17.875
516000,3309191,18.203
517000,3316074,18.062
518000,3322957,18.234
519000,3329842,18.219
520000,3336727,18.281
521000,3343613,18.297
522000,3350500,18.391
523000,3357388,18.266
524000,3364277,18.453
525000,3371166,18.562
526000,3378057,18.422
527000,3384949,18.359
528000,3391841,18.578
529000,3398734,18.781
530000,3405628,18.328
531000,3412523,18.766
532000,3419419,18.906
533000,3426316,18.812
534000,3433214,18.891
535000,3440112,19.000
536000,3447012,18.906
537000,3453912,19.016
538000,3460813,19.047
539000,3467715,19.109
540000,3474618,19.141
541000,3481521,19.156
542000,3488426,19.219
543000,3495331,19.281
544000,3502238,19.250
545000,3509145,19.312
546000,3516053,19.406
547000,3522962,19.391
548000,3529872,19.312
549000,3536782,19.484
550000,3543694,19.578
551000,3550606,19.578
552000,3557519,19.625
553000,3564433,19.531
554000,3571348,19.812
555000,3578263,19.781
556000,3585180,19.734
557000,3592097,19.797
558000,3599015,19.844
559000,3605934,19.875
560000,3612854,19.953
561000,3619775,19.984
562000,3626696,20.000
563000,3633619,20.062
564000,3640542,20.094
565000,3647466,20.125
566000,3654391,20.172
567000,3661316,20.141
568000,3668243,20.234
569000,3675170,20.203
570000,3682098,20.344
571000,3689027,20.281
572000,3695957,20.391
573000,3702887,20.484
574000,3709819,20.438
575000,3716751,20.531
576000,3723684,20.609
577000,3730617,20.609
578000,3737552,20.594
579000,3744487,20.703
580000,3751423,20.672
581000,3758360,20.750
582000,3765298,20.750
583000,3772237,20.828
584000,3779176,20.969
585000,3786116,20.922
586000,3793057,20.938
587000,3799999,21.016
588000,3806941,21.031
589000,3813885,21.156
590000,3820829,21.172
591000,3827774,21.250
592000,3834719,21.203
593000,3841666,21.250
594000,3848613,21.250
595000,3855561,21.266
596000,3862510,21.469
597000,3869459,21.344
598000,3876410,21.406
599000,3883361,21.453
600000,3890313,21.562
601000,3897266,21.516
602000,3904219,21.562
603000,3911173,21.703
604000,3918128,21.625
605000,3925084,21.672
606000,3932041,21.797
607000,3938998,21.656
608000,3945956,21.750
609000,3952915,21.891
610000,3959875,21.906
611000,3966835,21.938
612000,3973797,21.953
613000,3980759,22.031
614000,3987721,22.109
615000,3994685,22.078
616000,4001649,22.094
617000,4008614,22.156
618000,4015580,22.125
619000,4022546,22.156
620000,4029513,22.250
621000,4036481,22.312
622000,4043450,22.359
623000,4050420,22.375
624000,4057390,22.484
625000,4064361,22.500
626000,4071333,22.547
627000,4078305,22.547
628000,4085278,22.594
629000,4092252,22.547
630000,4099227,22.594
631000,4106202,22.625
632000,4113178,22.750
633000,4120155,22.703
634000,4127133,22.797
635000,4134111,22.906
636000,4141091,22.938
637000,4148070,22.844
638000,4155051,23.031
639000,4162032,23.031
640000,4169014,23.031
641000,4175997,23.141
642000,4182981,23.156
643000,4189965,23.188
644000,4196950,23.344
645000,4203935,23.281
646000,4210922,23.344
647000,4217909,23.297
648000,4224897,23.391
649000,4231885,23.547
650000,4238874,23.500
651000,4245864,23.609
652000,4252855,23.578
653000,4259846,23.562
654000,4266839,23.703
655000,4273831,23.688
656000,4280825,23.797
657000,4287819,23.781
658000,4294814,23.781
659000,4301810,23.891
660000,4308806,23.938
661000,4315803,23.906
662000,4322801,23.984
663000,4329800,24.031
664000,4336799,24.047
665000,4343799,24.172
666000,4350799,24.078
667000,4357801,24.078
668000,4364803,24.219
669000,4371805,24.250
670000,4378809,24.312
671000,4385813,24.391
672000,4392818,24.391
673000,4399823,24.484
674000,4406829,24.484
675000,4413836,24.578
676000,4420844,24.516
677000,4427852,24.578
678000,4434861,24.703
679000,4441871,24.703
680000,4448881,24.734
681000,4455892,24.812
682000,4462904,24.797
683000,4469916,24.734
684000,4476929,24.906
685000,4483943,24.844
686000,4490957,24.953
687000,4497972,24.922
688000,4504988,25.016
689000,4512005,25.078
690000,4519022,25.078
691000,4526040,25.094
692000,4533058,25.188
693000,4540077,25.188
694000,4547097,25.219
695000,4554117,25.281
696000,4561139,25.250
697000,4568160,25.297
698000,4575183,25.281
699000,4582206,25.422
700000,4589230,25.266
701000,4596254,25.547
702000,4603279,25.109
703000,4610305,25.188
704000,4617331,25.062
705000,4624359,25.578
706000,4631386,25.703
707000,4638415,25.641
708000,4645444,25.422
709000,4652473,25.672
710000,4659504,25.781
711000,4666535,25.672
712000,4673567,25.703
713000,4680599,25.688
714000,4687632,25.781
715000,4694665,26.234
716000,4701700,25.969
717000,4708735,26.172
718000,4715770,26.172
719000,4722807,26.281
720000,4729843,26.234
721000,4736881,26.234
722000,4743919,26.516
723000,4750958,26.578
724000,4757997,26.578
725000,4765038,26.609
726000,4772078,26.625
727000,4779120,26.688
728000,4786162,26.703
729000,4793204,26.750
730000,4800248,26.844
731000,4807292,26.844
732000,4814336,26.922
733000,4821381,26.953
734000,4828427,26.938
735000,4835474,27.000
736000,4842521,27.094
737000,4849568,27.141
738000,4856617,27.156
739000,4863666,27.219
740000,4870715,27.234
741000,4877766,27.281
742000,4884817,27.328
743000,4891868,27.375
744000,4898920,27.438
745000,4905973,27.469
746000,4913026,27.516
747000,4920080,27.531
748000,4927135,27.594
749000,4934190,27.672
750000,4941246,27.688
751000,4948303,27.719
752000,4955360,27.750
753000,4962418,27.469
754000,4969476,27.734
755000,4976535,27.766
756000,4983595,27.812
757000,4990655,27.875
758000,4997716,27.859
759000,5004777,27.938
760000,5011839,28.000
761000,5018902,28.031
762000,5025965,28.031
763000,5033029,28.109
764000,5040093,28.125
765000,5047158,28.156
766000,5054224,28.219
767000,5061290,28.250
768000,5068357,28.297
769000,5075425,28.344
770000,5082493,28.391
771000,5089562,28.375
772000,5096631,28.469
773000,5103701,28.500
774000,5110771,28.531
775000,5117842,28.594
776000,5124914,28.500
777000,5131986,28.641
778000,5139059,28.703
779000,5146133,28.766
780000,5153207,28.812
781000,5160282,28.797
782000,5167357,28.875
783000,5174433,28.922
784000,5181509,28.953
785000,5188587,29.016
786000,5195664,28.984
787000,5202742,29.078
788000,5209821,29.109
789000,5216901,29.156
790000,5223981,29.219
791000,5231061,29.219
792000,5238143,29.297
793000,5245224,29.312
794000,5252307,29.344
795000,5259390,29.344
796000,5266473,29.422
797000,5273558,29.453
798000,5280642,29.484
799000,5287728,29.531
800000,5294813,29.578
801000,5301900,29.609
802000,5308987,29.656
803000,5316075,29.672
804000,5323163,29.672
805000,5330252,29.797
806000,5337341,29.812
807000,5344431,29.891
808000,5351521,29.891
809000,5358613,29.969
810000,5365704,29.969
811000,5372796,30.031
812000,5379889,30.109
813000,5386983,30.078
814000,5394077,30.203
815000,5401171,30.188
816000,5408266,30.234
817000,5415362,30.281
818000,5422458,30.281
819000,5429555,30.359
820000,5436652,30.391
821000,5443750,30.453
822000,5450849,30.516
823000,5457948,30.562
824000,5465047,30.578
825000,5472147,30.641
826000,5479248,30.688
827000,5486350,30.688
828000,5493451,30.750
829000,5500554,30.781
830000,5507657,30.828
831000,5514760,30.875
832000,5521865,30.938
833000,5528969,30.922
834000,5536074,30.984
835000,5543180,31.078
836000,5550287,30.984
837000,5557393,31.109
838000,5564501,31.156
839000,5571609,31.188
840000,5578717,31.250
841000,5585826,31.297
842000,5592936,31.344
843000,5600046,31.391
844000,5607157,31.391
845000,5614268,31.469
846000,5621380,31.469
847000,5628493,31.547
848000,5635606,31.578
849000,5642719,31.609
850000,5649833,31.641
851000,5656948,31.703
852000,5664063,31.750
853000,5671179,31.812
854000,5678295,31.859
855000,5685412,31.844
856000,5692529,31.875
857000,5699647,31.953
858000,5706766,32.000
859000,5713885,32.047
860000,5721004,32.078
861000,5728124,32.094
862000,5735245,32.109
863000,5742366,32.203
864000,5749488,32.219
865000,5756610,32.266
866000,5763733,32.312
867000,5770856,32.344
868000,5777980,32.422
869000,5785105,32.438
870000,5792229,32.484
871000,5799355,32.547
872000,5806481,32.594
873000,5813607,32.578
874000,5820734,32.672
875000,5827862,32.688
876000,5834990,32.734
877000,5842119,32.781
878000,5849248,32.797
879000,5856378,32.859
880000,5863508,32.906
881000,5870639,32.969
882000,5877770,33.000
883000,5884902,33.031
884000,5892034,33.062
885000,5899167,33.125
886000,5906301,33.172
887000,5913435,33.219
888000,5920569,33.266
889000,5927704,33.297
890000,5934840,33.344
891000,5941976,33.344
892000,5949112,33.312
893000,5956249,33.453
894000,5963387,33.516
895000,5970525,33.547
896000,5977664,33.531
897000,5984803,33.609
898000,5991942,33.672
899000,5999083,33.734
900000,6006223,33.750
901000,6013364,33.797
902000,6020506,33.859
903000,6027648,33.906
904000,6034791,33.922
905000,6041934,33.969
906000,6049078,34.047
907000,6056222,34.078
908000,6063367,34.094
909000,6070513,34.156
910000,6077658,34.203
911000,6084805,34.250
912000,6091952,34.281
913000,6099099,34.328
914000,6106247,34.406
915000,6113395,34.406
916000,6120544,34.422
917000,6127693,34.531
918000,6134843,34.531
919000,6141994,34.578
920000,6149145,34.594
921000,6156296,34.672
922000,6163448,34.703
923000,6170600,34.750
924000,6177753,34.781
925000,6184907,34.797
926000,6192061,34.875
927000,6199215,34.938
928000,6206370,34.922
929000,6213526,35.000
930000,6220682,35.047
931000,6227838,35.078
932000,6234995,35.156
933000,6242152,35.188
934000,6249310,35.234
935000,6256469,35.203
936000,6263628,35.250
937000,6270787,35.234
938000,6277947,35.359
939000,6285107,35.406
940000,6292268,35.438
941000,6299429,35.453
942000,6306591,35.500
943000,6313754,35.547
944000,6320917,35.469
945000,6328080,35.625
946000,6335244,35.703
947000,6342408,35.703
948000,6349573,35.781
949000,6356738,35.812
950000,6363904,35.844
951000,6371070,35.891
952000,6378237,35.922
953000,6385405,35.922
954000,6392572,36.016
955000,6399741,36.047
956000,6406909,36.047
957000,6414079,36.078
958000,6421248,36.109
959000,6428418,36.172
960000,6435589,36.188
961000,6442760,36.281
962000,6449932,36.219
963000,6457104,36.312
964000,6464277,36.328
965000,6471450,35.078
966000,6478623,32.609
967000,6485797,32.688
968000,6492972,32.750
969000,6500147,32.812
970000,6507322,32.828
971000,6514498,32.859
972000,6521675,32.875
973000,6528852,32.922
974000,6536029,32.938
975000,6543207,33.000
976000,6550386,33.000
977000,6557564,33.078
978000,6564744,33.109
979000,6571924,33.172
980000,6579104,33.172
981000,6586285,33.203
982000,6593466,33.234
983000,6600648,33.312
984000,6607830,33.281
985000,6615012,33.375
986000,6622196,33.422
987000,6629379,33.453
988000,6636563,33.453
989000,6643748,33.516
990000,6650933,33.562
991000,6658118,33.578
992000,6665304,33.641
993000,6672490,33.688
994000,6679677,33.703
995000,6686865,33.750
996000,6694053,33.766
997000,6701241,33.859
998000,6708430,33.859
999000,6715619,33.875
1000000,6722809,33.969
</pre>
:Happy plotting! [[User:Dinosaur|Dinosaur]] ([[User talk:Dinosaur|talk]]) 02:45, 10 April 2016 (UTC)
|
Latest revision as of 04:28, 22 March 2020
PARI/GP you speak about factor tree, but only primes are used, where is the advantage??? I love such solutions like in perl <lang perl>use ntheory qw(pn_primorial); say "First ten primorials: ", join ", ", map { pn_primorial($_) } 0..9;</lang> and all is done ;-) Horsth
- I just added a version using the new vecprod command. It is quite a bit faster. It uses a product tree for efficient large vector products -- the old comment was misleading about using a factor tree. Danaj (talk) 16:50, 9 October 2018 (UTC)
- Once I figured out what a "product tree" is, simply multiplying in pairs (technically adjacent, not that my Phix entry does that) I was positively shocked to see a better than 50-fold performance improvement (6 mins => 6 secs). --Pete Lomax (talk) 04:28, 22 March 2020 (UTC)
a faster-than-exponential growth rate in CPU time stated by dinosaur
Story
school - multiplication ist quadratic in runtime O(count of digits) ~ (count of digits)^2
Prime(100000) = 1299709, Primorial(100000) ~ 0.1909604E+563921 121.547 seconds. Prime(1000000) = 15485863, Primorial(1000000) ~ 0.1147175E+6722809 17756.797 seconds.
10-times Numbers -> ~100-times runtime 121*100-> 12100
the digitcount of the numbers one multiplies grew be a factor of lg10(15.45Mio)/lg10(1.299Mio) =1,17
so you get 10-> (1.17*10) ^ 2 = 136,89*121,547= 16638 thats not far from 17756
Now take into account that the number gets so big, that it doesn't fit in level3 Cache ,which slow things down.Only 3% will be enough 121,547*(1.17*1.03*10)^2 s = 17651 s Horsth
The implementation of primorial I am using, running on this laptop, took 0.002909 seconds for primorial 100000 and 0.049093 seconds for primorial 1000000. With digit counts, that became 0.004267 seconds and 0.04369 seconds. I guess that's faster than exponential growth rate if by fast you mean the execution time... but ... actually, I'm not sure where I'm going with this. I am mildly surprised that digit count could be faster than the raw primorial but that might just be random variation --Rdm (talk) 20:41, 8 April 2016 (UTC) Edit: System Info claims I'm working with an i7: 2.8GHz clock, 256KB L2, 6MB L3 - no mention of L1. --Rdm (talk) 09:26, 9 April 2016 (UTC)
- According to System Info, the computer has 64KB of L1 I-cache, 16KB L1 D-cache, and 2048KB of L2 cache, with further jargon about 2 way set associative, 64 byte line size, etc. and no mention of L3. Later, I see that the GIMP calculation gives 8MB for L3 on this AMD k10. However, I have no idea how much of each resource is devoted to the various activities such as running the GIMP crunch and windows itself. This is why experimental timings are tricky to perform as well as being a load on the patience. I am however surprised by the speeds quoted by some contributors, given that towards the end the number has millions of digits.
- As for the standard multiplication procedure of n digits by m digits consuming time proportional to n.m, remember that my version cheats by using a one digit multiplicand (err, the second number in a*b) even though it is much larger than the base of arithmetic. Computer crunching of integers is unaffected by whether x is multiplied by 12 or 1234567, except for overflows. Thus, its running time should be proportional to n, the number of digits in the big number. In principle, and ignoring caches. If successive primorials were attained by multiplying by a constant, then that number of digits would increase linearly, but of course the multiplicand is increasing in size itself. If that increase was the same as with factorials then the number of digits would increase according to log(x!) which is proportional to x*log(x) via Stirling's approximation, which is to say a linear growth (the x) multiplied by a factor that grows ever more slowly (the log(x))
- But Primorial(x) grows even faster than x! However, I didn't look and think long about the cpu timings before making the remark about "faster than exponential". I shall twiddle the prog. to produce more reports on timing... Dinosaur (talk) 08:51, 9 April 2016 (UTC)
- On reading http://rosettacode.org/mw/index.php?title=Primorial_numbers&type=revision&diff=225184&oldid=225110 I think I'm beginning to understand your point of view. I guess the issue is "in proportion to what?" For example, if we consider resource consumption (quite a lot) in proportion to the number of arguments (always just one), resource growth is infinite. If we think of resource growth in proportion to the number of digits in the argument we get "resource consumption (time to complete) growth faster than exponential". If we think of resource growth in proportion to the numerical value of the argument time consumed growth grows faster than linear.
- Anyways, I guess a general issue here is that we tend to think in "shorthand" and when relating those thought to other people it often takes some extra work to make sure they understand our thinking. --Rdm (talk) 01:58, 10 April 2016 (UTC)
- Our edits clashed! In the article I have rephrased the usage of "exponential" to note that it is the task that is growing exponentially (n = 10^i for i = 1, 2, 3, ...) so that even for a linear exercise, the work would grow exponentially. But here there is a further growth factor beyond the linear, because the number size is growing faster than linear, because n is growing... The supposition being that a multiply is linear in (number of digits) given that the multiplicand is one (embolismic) digit only. Except, we know that sooner or later, its digit count will grow. The unit of "sizeness" is not always obvious or convenient. To calculate Primorial(n) the task size is obviously determined by the value of n, from which is deduced log(n) for the number of digits both of n itself and Primorial(n) and one argues about the time for a multiply with those sizes of digit strings, and then perhaps the integration of those times so as to reach n from 1. All of which depends on n. But, since digit string length is so important, one might choose to talk about log(n) as being the unit of size. In the factoring of numbers, for example, I (and Prof. Knuth) speak of n and sqrt(n), but, with ever larger n, it seems now it is fashionable to use log(n) as the unit, and speak of "polynomial time in N" or similar, when N is actually log(n)
- Righto, another overnight run, this time with a report every thousand for n, d, and t where t is the cpu time to attain n after reaching n - 1000. So, from 99000 to attain 100000 the digit count went from 557809 to 563921 and the cpu time was 2·625. For 999000 to 1000000 the digit count went from 6715619 to 6722809 and the cpu time was 33·969. Plotting showed almost linear growth rates across this limited span:
Correlation 0·99990 t = d*5·636E-6 -0·41458 0·99973 d = n*6·6983 -125797·8 0·99943 t = n*3·7744E-5 - 1·1205
- These were for data only up to n = 800,000 because there was a change in slope subsequently, probably because I stopped using the computer for other minor activity and thus didn't disrupt its various buffers. The Mersenne prime calculations continued. The points wobble above and below the fitted line across the span, and there is a bend visible at the start where the overall line is too low. That is, at the start the calculation is going a little faster and presumably, one could talk about not yet overflowing some on-chip memory buffer as another reason for non-linearity. Similarly, at the high end the points start to rise above the fitted line, and one could talk about a growth factor such as log(n) rather than a constant. This is obscured by the greater speed later on when I had walked away from the toiling computer. Nevertheless, one can see that a slight curve is being approximated by a straight line over a limited span, which means that using the start to attempt to identify the effect of a cpu buffer size will be tricky. Even so, a log(n) vs. log(t) plot shows a change of slope at the start - except that is for only the first few points. Alas, with "only" a few thousand digits to the big number, the resolution of the CPU timing function is insufficient to show finer details, and repeating the calculation a hundred times (say) will require auxiliary storage to enable the repetition and this will change the workings of the presumed buffering processes away from what was intended to be investigated. A frustrating business.
- Unfortunately, there is no provision for posting images, and anyway I've had a lot of trouble with Octave producing damaged plot files (.svg, .png, etc.) having to resort to screen image captures, so instead, here are the data:
- Pox! I have just created file Primorial.cpuTime.svg, but, "Error creating thumbnail: /bin/bash: rsvg-convert: command not found" results. Inkscape however draws the plot without difficulty, though at 657KB the file is a bit large for just a thousand points, a line, and some annotation. And now that it is uploaded, I can't see how to delete it. I shall attempt to replace it by a screen capture. As for Octave, it won't "Print" the plot as either a .png nor a .jpg due to some complaint of its own "'C:\Program' is not recognized as an internal or external command, operable program or batch file." so a tar pit there.
- The calculation of the primes is not a problem, because all million are prepared in array PRIME before any Primorial attempts are made, and the time for this is somewhere in the blink of starting the run and the first Primorial results appearing even as the screen window manifests. Dinosaur (talk) 06:30, 10 April 2016 (UTC)
And here is a plot of cpu time against the number of digits in the big number, which is successively being multiplied by a single digit value.
- Only admins are allowed to delete files. I've removed "Primorial.cpuTime.svg". --Andreas Perstinger (talk) 18:36, 10 April 2016 (UTC)
Grist
1000, 3393, 0.000 2000, 7483, 0.016 3000, 11829, 0.047 4000, 16340, 0.047 5000, 20975, 0.078 6000, 25706, 0.094 7000, 30519, 0.109 8000, 35400, 0.141 9000, 40342, 0.156 10000, 45337, 0.172 11000, 50381, 0.219 12000, 55468, 0.203 13000, 60595, 0.250 14000, 65759, 0.266 15000, 70957, 0.250 16000, 76187, 0.328 17000, 81447, 0.344 18000, 86735, 0.359 19000, 92050, 0.391 20000, 97389, 0.406 21000, 102753, 0.422 22000, 108139, 0.469 23000, 113547, 0.484 24000, 118975, 0.500 25000, 124424, 0.531 26000, 129891, 0.562 27000, 135377, 0.578 28000, 140881, 0.609 29000, 146401, 0.625 30000, 151937, 0.656 31000, 157490, 0.703 32000, 163057, 0.688 33000, 168640, 0.750 34000, 174237, 0.766 35000, 179849, 0.750 36000, 185473, 0.797 37000, 191111, 0.812 38000, 196762, 0.859 39000, 202425, 0.891 40000, 208100, 0.906 41000, 213787, 0.938 42000, 219486, 0.953 43000, 225196, 1.000 44000, 230916, 1.016 45000, 236648, 1.047 46000, 242390, 1.062 47000, 248143, 1.094 48000, 253905, 1.156 49000, 259678, 1.156 50000, 265460, 1.156 51000, 271251, 1.203 52000, 277052, 1.234 53000, 282862, 1.234 54000, 288681, 1.297 55000, 294508, 1.297 56000, 300345, 1.328 57000, 306189, 1.359 58000, 312042, 1.406 59000, 317903, 1.422 60000, 323772, 1.453 61000, 329649, 1.484 62000, 335534, 1.516 63000, 341426, 1.531 64000, 347326, 1.562 65000, 353233, 1.594 66000, 359148, 1.609 67000, 365069, 1.641 68000, 370998, 1.688 69000, 376933, 1.719 70000, 382876, 1.719 71000, 388825, 1.719 72000, 394780, 1.766 73000, 400743, 1.812 74000, 406711, 1.844 75000, 412686, 1.875 76000, 418668, 1.922 77000, 424656, 1.938 78000, 430649, 1.938 79000, 436649, 1.969 80000, 442655, 2.016 81000, 448667, 2.047 82000, 454684, 2.062 83000, 460708, 2.109 84000, 466737, 2.141 85000, 472772, 2.156 86000, 478812, 2.281 87000, 484857, 2.234 88000, 490908, 2.281 89000, 496965, 2.297 90000, 503026, 2.328 91000, 509093, 2.359 92000, 515165, 2.391 93000, 521242, 2.422 94000, 527324, 2.438 95000, 533411, 2.500 96000, 539504, 2.516 97000, 545601, 2.547 98000, 551703, 2.578 99000, 557809, 2.594 100000, 563921, 2.625 101000, 570037, 2.656 102000, 576158, 2.672 103000, 582283, 2.719 104000, 588413, 2.750 105000, 594548, 2.797 106000, 600687, 2.812 107000, 606831, 2.859 108000, 612978, 2.891 109000, 619131, 2.922 110000, 625287, 2.969 111000, 631448, 2.984 112000, 637613, 3.047 113000, 643782, 3.094 114000, 649956, 3.094 115000, 656133, 3.156 116000, 662315, 3.156 117000, 668500, 3.203 118000, 674690, 3.281 119000, 680884, 3.297 120000, 687081, 3.344 121000, 693283, 3.359 122000, 699488, 3.422 123000, 705698, 3.453 124000, 711911, 3.500 125000, 718128, 3.516 126000, 724349, 3.547 127000, 730573, 3.625 128000, 736801, 3.672 129000, 743033, 3.703 130000, 749268, 3.734 131000, 755507, 3.797 132000, 761750, 3.828 133000, 767996, 3.875 134000, 774246, 3.922 135000, 780499, 3.953 136000, 786756, 3.984 137000, 793016, 4.047 138000, 799280, 4.062 139000, 805547, 4.141 140000, 811817, 4.172 141000, 818091, 4.188 142000, 824368, 4.250 143000, 830648, 4.281 144000, 836932, 4.312 145000, 843219, 4.375 146000, 849509, 4.391 147000, 855802, 4.422 148000, 862099, 4.438 149000, 868398, 4.500 150000, 874701, 4.547 151000, 881007, 4.578 152000, 887316, 4.641 153000, 893628, 4.688 154000, 899943, 4.688 155000, 906261, 4.750 156000, 912583, 4.766 157000, 918907, 4.781 158000, 925234, 4.859 159000, 931564, 4.875 160000, 937898, 4.922 161000, 944234, 4.984 162000, 950573, 4.984 163000, 956915, 5.016 164000, 963259, 5.078 165000, 969607, 5.094 166000, 975958, 5.109 167000, 982311, 5.188 168000, 988667, 5.203 169000, 995026, 5.156 170000,1001388, 5.219 171000,1007752, 5.312 172000,1014119, 5.328 173000,1020489, 5.375 174000,1026862, 5.391 175000,1033238, 5.484 176000,1039616, 5.500 177000,1045997, 5.484 178000,1052380, 5.562 179000,1058766, 5.594 180000,1065155, 5.656 181000,1071546, 5.656 182000,1077940, 5.703 183000,1084336, 5.688 184000,1090735, 5.750 185000,1097137, 5.812 186000,1103541, 5.875 187000,1109948, 5.906 188000,1116357, 5.922 189000,1122768, 5.891 190000,1129182, 6.000 191000,1135599, 6.016 192000,1142018, 6.047 193000,1148439, 6.109 194000,1154863, 6.094 195000,1161290, 6.172 196000,1167718, 6.188 197000,1174149, 6.250 198000,1180583, 6.250 199000,1187018, 6.297 200000,1193457, 6.344 201000,1199897, 6.359 202000,1206340, 6.406 203000,1212785, 6.438 204000,1219233, 6.469 205000,1225682, 6.516 206000,1232134, 6.547 207000,1238588, 6.578 208000,1245045, 6.609 209000,1251504, 6.609 210000,1257965, 6.703 211000,1264428, 6.750 212000,1270893, 6.734 213000,1277361, 6.828 214000,1283831, 6.859 215000,1290303, 6.859 216000,1296777, 6.938 217000,1303254, 6.953 218000,1309732, 7.000 219000,1316213, 7.047 220000,1322696, 7.047 221000,1329181, 7.141 222000,1335668, 7.125 223000,1342158, 7.188 224000,1348649, 7.203 225000,1355143, 7.281 226000,1361638, 7.266 227000,1368136, 7.328 228000,1374635, 7.344 229000,1381137, 7.406 230000,1387641, 7.406 231000,1394147, 7.484 232000,1400654, 7.516 233000,1407164, 7.531 234000,1413676, 7.594 235000,1420189, 7.609 236000,1426705, 7.609 237000,1433223, 7.703 238000,1439742, 7.719 239000,1446264, 7.734 240000,1452788, 7.812 241000,1459313, 7.828 242000,1465841, 7.891 243000,1472370, 7.938 244000,1478902, 7.875 245000,1485435, 7.938 246000,1491970, 8.031 247000,1498507, 8.078 248000,1505046, 8.094 249000,1511587, 8.094 250000,1518130, 8.203 251000,1524675, 8.219 252000,1531221, 8.250 253000,1537770, 8.266 254000,1544320, 8.328 255000,1550873, 8.344 256000,1557427, 8.391 257000,1563983, 8.422 258000,1570540, 8.484 259000,1577100, 8.500 260000,1583661, 8.531 261000,1590224, 8.562 262000,1596789, 8.609 263000,1603355, 8.656 264000,1609924, 8.672 265000,1616494, 8.719 266000,1623066, 8.672 267000,1629640, 8.750 268000,1636215, 8.812 269000,1642792, 8.875 270000,1649371, 8.859 271000,1655952, 8.906 272000,1662534, 8.984 273000,1669118, 9.031 274000,1675704, 9.047 275000,1682291, 9.109 276000,1688881, 9.109 277000,1695472, 9.141 278000,1702064, 9.188 279000,1708658, 9.250 280000,1715254, 9.297 281000,1721852, 9.297 282000,1728451, 9.312 283000,1735052, 9.375 284000,1741655, 9.406 285000,1748259, 9.391 286000,1754865, 9.516 287000,1761472, 9.516 288000,1768082, 9.578 289000,1774692, 9.594 290000,1781305, 9.625 291000,1787919, 9.703 292000,1794534, 9.734 293000,1801151, 9.750 294000,1807770, 9.781 295000,1814391, 9.828 296000,1821013, 9.859 297000,1827636, 9.844 298000,1834261, 9.906 299000,1840888, 9.938 300000,1847516, 9.953 301000,1854146, 9.969 302000,1860777,10.047 303000,1867410,10.094 304000,1874045,10.109 305000,1880681,10.203 306000,1887318,10.047 307000,1893958,10.250 308000,1900598,10.281 309000,1907240,10.250 310000,1913884,10.328 311000,1920529,10.422 312000,1927176,10.438 313000,1933824,10.500 314000,1940474,10.547 315000,1947125,10.516 316000,1953777,10.359 317000,1960431,10.547 318000,1967087,10.578 319000,1973744,10.719 320000,1980402,10.688 321000,1987062,10.781 322000,1993724,10.719 323000,2000387,10.828 324000,2007051,10.875 325000,2013717,10.594 326000,2020384,10.859 327000,2027052,11.016 328000,2033722,11.062 329000,2040394,11.031 330000,2047067,11.156 331000,2053741,11.078 332000,2060417,11.125 333000,2067094,11.188 334000,2073772,11.297 335000,2080452,11.297 336000,2087133,11.344 337000,2093816,11.297 338000,2100500,11.359 339000,2107186,11.391 340000,2113873,11.453 341000,2120561,11.516 342000,2127250,11.562 343000,2133941,11.438 344000,2140633,11.625 345000,2147327,11.609 346000,2154022,11.656 347000,2160718,11.688 348000,2167416,11.641 349000,2174115,11.781 350000,2180815,11.859 351000,2187517,11.812 352000,2194220,11.938 353000,2200924,11.953 354000,2207630,11.984 355000,2214337,12.062 356000,2221045,12.078 357000,2227755,12.109 358000,2234466,11.953 359000,2241178,12.172 360000,2247891,12.141 361000,2254606,12.219 362000,2261322,12.344 363000,2268040,12.156 364000,2274758,12.281 365000,2281478,12.375 366000,2288199,12.406 367000,2294922,12.250 368000,2301646,12.484 369000,2308371,12.500 370000,2315097,12.641 371000,2321825,12.484 372000,2328553,12.453 373000,2335283,12.766 374000,2342015,12.734 375000,2348747,12.750 376000,2355481,12.844 377000,2362216,12.812 378000,2368952,12.750 379000,2375690,12.859 380000,2382429,12.875 381000,2389169,12.906 382000,2395910,13.031 383000,2402652,13.031 384000,2409396,13.094 385000,2416141,13.125 386000,2422887,13.250 387000,2429635,13.250 388000,2436383,13.219 389000,2443133,13.312 390000,2449884,13.312 391000,2456636,13.203 392000,2463389,13.469 393000,2470144,13.344 394000,2476900,13.453 395000,2483657,13.547 396000,2490415,13.594 397000,2497174,13.609 398000,2503935,13.641 399000,2510696,13.672 400000,2517459,13.781 401000,2524223,13.766 402000,2530988,13.859 403000,2537755,13.828 404000,2544522,13.812 405000,2551291,13.797 406000,2558061,13.906 407000,2564832,13.812 408000,2571604,14.000 409000,2578377,14.047 410000,2585151,14.016 411000,2591927,14.125 412000,2598703,14.094 413000,2605481,14.125 414000,2612260,14.234 415000,2619040,14.250 416000,2625821,14.266 417000,2632603,14.375 418000,2639387,14.312 419000,2646171,14.375 420000,2652957,14.500 421000,2659743,14.484 422000,2666531,14.438 423000,2673320,14.578 424000,2680110,14.531 425000,2686901,14.578 426000,2693694,14.641 427000,2700487,14.719 428000,2707281,14.781 429000,2714077,14.750 430000,2720873,14.812 431000,2727671,14.844 432000,2734470,14.766 433000,2741270,14.906 434000,2748071,14.969 435000,2754873,14.969 436000,2761676,14.938 437000,2768480,14.984 438000,2775285,15.000 439000,2782091,15.266 440000,2788899,15.219 441000,2795707,15.359 442000,2802516,15.312 443000,2809327,15.375 444000,2816139,15.406 445000,2822951,15.422 446000,2829765,15.484 447000,2836580,15.562 448000,2843395,15.625 449000,2850212,15.656 450000,2857030,15.672 451000,2863849,15.766 452000,2870669,15.672 453000,2877490,15.781 454000,2884312,15.750 455000,2891135,15.859 456000,2897959,15.906 457000,2904784,15.797 458000,2911610,15.594 459000,2918437,15.547 460000,2925265,15.609 461000,2932094,15.891 462000,2938924,16.109 463000,2945755,16.094 464000,2952587,16.172 465000,2959420,16.172 466000,2966255,16.297 467000,2973090,16.281 468000,2979926,16.203 469000,2986763,16.328 470000,2993601,16.375 471000,3000440,16.422 472000,3007280,16.484 473000,3014121,16.516 474000,3020963,16.578 475000,3027806,16.641 476000,3034650,16.594 477000,3041495,16.547 478000,3048341,16.703 479000,3055188,16.688 480000,3062036,16.797 481000,3068885,16.812 482000,3075734,16.750 483000,3082585,16.828 484000,3089437,16.922 485000,3096290,16.875 486000,3103143,16.969 487000,3109998,17.047 488000,3116853,17.031 489000,3123710,17.031 490000,3130568,17.172 491000,3137426,17.141 492000,3144285,17.188 493000,3151146,17.297 494000,3158007,17.344 495000,3164869,17.375 496000,3171732,17.359 497000,3178597,17.453 498000,3185462,17.453 499000,3192328,17.469 500000,3199195,17.562 501000,3206062,17.547 502000,3212931,17.562 503000,3219801,17.781 504000,3226672,17.812 505000,3233543,17.797 506000,3240416,17.766 507000,3247289,17.844 508000,3254163,17.938 509000,3261039,17.969 510000,3267915,17.969 511000,3274792,18.078 512000,3281670,18.062 513000,3288549,18.062 514000,3295429,18.078 515000,3302310,17.875 516000,3309191,18.203 517000,3316074,18.062 518000,3322957,18.234 519000,3329842,18.219 520000,3336727,18.281 521000,3343613,18.297 522000,3350500,18.391 523000,3357388,18.266 524000,3364277,18.453 525000,3371166,18.562 526000,3378057,18.422 527000,3384949,18.359 528000,3391841,18.578 529000,3398734,18.781 530000,3405628,18.328 531000,3412523,18.766 532000,3419419,18.906 533000,3426316,18.812 534000,3433214,18.891 535000,3440112,19.000 536000,3447012,18.906 537000,3453912,19.016 538000,3460813,19.047 539000,3467715,19.109 540000,3474618,19.141 541000,3481521,19.156 542000,3488426,19.219 543000,3495331,19.281 544000,3502238,19.250 545000,3509145,19.312 546000,3516053,19.406 547000,3522962,19.391 548000,3529872,19.312 549000,3536782,19.484 550000,3543694,19.578 551000,3550606,19.578 552000,3557519,19.625 553000,3564433,19.531 554000,3571348,19.812 555000,3578263,19.781 556000,3585180,19.734 557000,3592097,19.797 558000,3599015,19.844 559000,3605934,19.875 560000,3612854,19.953 561000,3619775,19.984 562000,3626696,20.000 563000,3633619,20.062 564000,3640542,20.094 565000,3647466,20.125 566000,3654391,20.172 567000,3661316,20.141 568000,3668243,20.234 569000,3675170,20.203 570000,3682098,20.344 571000,3689027,20.281 572000,3695957,20.391 573000,3702887,20.484 574000,3709819,20.438 575000,3716751,20.531 576000,3723684,20.609 577000,3730617,20.609 578000,3737552,20.594 579000,3744487,20.703 580000,3751423,20.672 581000,3758360,20.750 582000,3765298,20.750 583000,3772237,20.828 584000,3779176,20.969 585000,3786116,20.922 586000,3793057,20.938 587000,3799999,21.016 588000,3806941,21.031 589000,3813885,21.156 590000,3820829,21.172 591000,3827774,21.250 592000,3834719,21.203 593000,3841666,21.250 594000,3848613,21.250 595000,3855561,21.266 596000,3862510,21.469 597000,3869459,21.344 598000,3876410,21.406 599000,3883361,21.453 600000,3890313,21.562 601000,3897266,21.516 602000,3904219,21.562 603000,3911173,21.703 604000,3918128,21.625 605000,3925084,21.672 606000,3932041,21.797 607000,3938998,21.656 608000,3945956,21.750 609000,3952915,21.891 610000,3959875,21.906 611000,3966835,21.938 612000,3973797,21.953 613000,3980759,22.031 614000,3987721,22.109 615000,3994685,22.078 616000,4001649,22.094 617000,4008614,22.156 618000,4015580,22.125 619000,4022546,22.156 620000,4029513,22.250 621000,4036481,22.312 622000,4043450,22.359 623000,4050420,22.375 624000,4057390,22.484 625000,4064361,22.500 626000,4071333,22.547 627000,4078305,22.547 628000,4085278,22.594 629000,4092252,22.547 630000,4099227,22.594 631000,4106202,22.625 632000,4113178,22.750 633000,4120155,22.703 634000,4127133,22.797 635000,4134111,22.906 636000,4141091,22.938 637000,4148070,22.844 638000,4155051,23.031 639000,4162032,23.031 640000,4169014,23.031 641000,4175997,23.141 642000,4182981,23.156 643000,4189965,23.188 644000,4196950,23.344 645000,4203935,23.281 646000,4210922,23.344 647000,4217909,23.297 648000,4224897,23.391 649000,4231885,23.547 650000,4238874,23.500 651000,4245864,23.609 652000,4252855,23.578 653000,4259846,23.562 654000,4266839,23.703 655000,4273831,23.688 656000,4280825,23.797 657000,4287819,23.781 658000,4294814,23.781 659000,4301810,23.891 660000,4308806,23.938 661000,4315803,23.906 662000,4322801,23.984 663000,4329800,24.031 664000,4336799,24.047 665000,4343799,24.172 666000,4350799,24.078 667000,4357801,24.078 668000,4364803,24.219 669000,4371805,24.250 670000,4378809,24.312 671000,4385813,24.391 672000,4392818,24.391 673000,4399823,24.484 674000,4406829,24.484 675000,4413836,24.578 676000,4420844,24.516 677000,4427852,24.578 678000,4434861,24.703 679000,4441871,24.703 680000,4448881,24.734 681000,4455892,24.812 682000,4462904,24.797 683000,4469916,24.734 684000,4476929,24.906 685000,4483943,24.844 686000,4490957,24.953 687000,4497972,24.922 688000,4504988,25.016 689000,4512005,25.078 690000,4519022,25.078 691000,4526040,25.094 692000,4533058,25.188 693000,4540077,25.188 694000,4547097,25.219 695000,4554117,25.281 696000,4561139,25.250 697000,4568160,25.297 698000,4575183,25.281 699000,4582206,25.422 700000,4589230,25.266 701000,4596254,25.547 702000,4603279,25.109 703000,4610305,25.188 704000,4617331,25.062 705000,4624359,25.578 706000,4631386,25.703 707000,4638415,25.641 708000,4645444,25.422 709000,4652473,25.672 710000,4659504,25.781 711000,4666535,25.672 712000,4673567,25.703 713000,4680599,25.688 714000,4687632,25.781 715000,4694665,26.234 716000,4701700,25.969 717000,4708735,26.172 718000,4715770,26.172 719000,4722807,26.281 720000,4729843,26.234 721000,4736881,26.234 722000,4743919,26.516 723000,4750958,26.578 724000,4757997,26.578 725000,4765038,26.609 726000,4772078,26.625 727000,4779120,26.688 728000,4786162,26.703 729000,4793204,26.750 730000,4800248,26.844 731000,4807292,26.844 732000,4814336,26.922 733000,4821381,26.953 734000,4828427,26.938 735000,4835474,27.000 736000,4842521,27.094 737000,4849568,27.141 738000,4856617,27.156 739000,4863666,27.219 740000,4870715,27.234 741000,4877766,27.281 742000,4884817,27.328 743000,4891868,27.375 744000,4898920,27.438 745000,4905973,27.469 746000,4913026,27.516 747000,4920080,27.531 748000,4927135,27.594 749000,4934190,27.672 750000,4941246,27.688 751000,4948303,27.719 752000,4955360,27.750 753000,4962418,27.469 754000,4969476,27.734 755000,4976535,27.766 756000,4983595,27.812 757000,4990655,27.875 758000,4997716,27.859 759000,5004777,27.938 760000,5011839,28.000 761000,5018902,28.031 762000,5025965,28.031 763000,5033029,28.109 764000,5040093,28.125 765000,5047158,28.156 766000,5054224,28.219 767000,5061290,28.250 768000,5068357,28.297 769000,5075425,28.344 770000,5082493,28.391 771000,5089562,28.375 772000,5096631,28.469 773000,5103701,28.500 774000,5110771,28.531 775000,5117842,28.594 776000,5124914,28.500 777000,5131986,28.641 778000,5139059,28.703 779000,5146133,28.766 780000,5153207,28.812 781000,5160282,28.797 782000,5167357,28.875 783000,5174433,28.922 784000,5181509,28.953 785000,5188587,29.016 786000,5195664,28.984 787000,5202742,29.078 788000,5209821,29.109 789000,5216901,29.156 790000,5223981,29.219 791000,5231061,29.219 792000,5238143,29.297 793000,5245224,29.312 794000,5252307,29.344 795000,5259390,29.344 796000,5266473,29.422 797000,5273558,29.453 798000,5280642,29.484 799000,5287728,29.531 800000,5294813,29.578 801000,5301900,29.609 802000,5308987,29.656 803000,5316075,29.672 804000,5323163,29.672 805000,5330252,29.797 806000,5337341,29.812 807000,5344431,29.891 808000,5351521,29.891 809000,5358613,29.969 810000,5365704,29.969 811000,5372796,30.031 812000,5379889,30.109 813000,5386983,30.078 814000,5394077,30.203 815000,5401171,30.188 816000,5408266,30.234 817000,5415362,30.281 818000,5422458,30.281 819000,5429555,30.359 820000,5436652,30.391 821000,5443750,30.453 822000,5450849,30.516 823000,5457948,30.562 824000,5465047,30.578 825000,5472147,30.641 826000,5479248,30.688 827000,5486350,30.688 828000,5493451,30.750 829000,5500554,30.781 830000,5507657,30.828 831000,5514760,30.875 832000,5521865,30.938 833000,5528969,30.922 834000,5536074,30.984 835000,5543180,31.078 836000,5550287,30.984 837000,5557393,31.109 838000,5564501,31.156 839000,5571609,31.188 840000,5578717,31.250 841000,5585826,31.297 842000,5592936,31.344 843000,5600046,31.391 844000,5607157,31.391 845000,5614268,31.469 846000,5621380,31.469 847000,5628493,31.547 848000,5635606,31.578 849000,5642719,31.609 850000,5649833,31.641 851000,5656948,31.703 852000,5664063,31.750 853000,5671179,31.812 854000,5678295,31.859 855000,5685412,31.844 856000,5692529,31.875 857000,5699647,31.953 858000,5706766,32.000 859000,5713885,32.047 860000,5721004,32.078 861000,5728124,32.094 862000,5735245,32.109 863000,5742366,32.203 864000,5749488,32.219 865000,5756610,32.266 866000,5763733,32.312 867000,5770856,32.344 868000,5777980,32.422 869000,5785105,32.438 870000,5792229,32.484 871000,5799355,32.547 872000,5806481,32.594 873000,5813607,32.578 874000,5820734,32.672 875000,5827862,32.688 876000,5834990,32.734 877000,5842119,32.781 878000,5849248,32.797 879000,5856378,32.859 880000,5863508,32.906 881000,5870639,32.969 882000,5877770,33.000 883000,5884902,33.031 884000,5892034,33.062 885000,5899167,33.125 886000,5906301,33.172 887000,5913435,33.219 888000,5920569,33.266 889000,5927704,33.297 890000,5934840,33.344 891000,5941976,33.344 892000,5949112,33.312 893000,5956249,33.453 894000,5963387,33.516 895000,5970525,33.547 896000,5977664,33.531 897000,5984803,33.609 898000,5991942,33.672 899000,5999083,33.734 900000,6006223,33.750 901000,6013364,33.797 902000,6020506,33.859 903000,6027648,33.906 904000,6034791,33.922 905000,6041934,33.969 906000,6049078,34.047 907000,6056222,34.078 908000,6063367,34.094 909000,6070513,34.156 910000,6077658,34.203 911000,6084805,34.250 912000,6091952,34.281 913000,6099099,34.328 914000,6106247,34.406 915000,6113395,34.406 916000,6120544,34.422 917000,6127693,34.531 918000,6134843,34.531 919000,6141994,34.578 920000,6149145,34.594 921000,6156296,34.672 922000,6163448,34.703 923000,6170600,34.750 924000,6177753,34.781 925000,6184907,34.797 926000,6192061,34.875 927000,6199215,34.938 928000,6206370,34.922 929000,6213526,35.000 930000,6220682,35.047 931000,6227838,35.078 932000,6234995,35.156 933000,6242152,35.188 934000,6249310,35.234 935000,6256469,35.203 936000,6263628,35.250 937000,6270787,35.234 938000,6277947,35.359 939000,6285107,35.406 940000,6292268,35.438 941000,6299429,35.453 942000,6306591,35.500 943000,6313754,35.547 944000,6320917,35.469 945000,6328080,35.625 946000,6335244,35.703 947000,6342408,35.703 948000,6349573,35.781 949000,6356738,35.812 950000,6363904,35.844 951000,6371070,35.891 952000,6378237,35.922 953000,6385405,35.922 954000,6392572,36.016 955000,6399741,36.047 956000,6406909,36.047 957000,6414079,36.078 958000,6421248,36.109 959000,6428418,36.172 960000,6435589,36.188 961000,6442760,36.281 962000,6449932,36.219 963000,6457104,36.312 964000,6464277,36.328 965000,6471450,35.078 966000,6478623,32.609 967000,6485797,32.688 968000,6492972,32.750 969000,6500147,32.812 970000,6507322,32.828 971000,6514498,32.859 972000,6521675,32.875 973000,6528852,32.922 974000,6536029,32.938 975000,6543207,33.000 976000,6550386,33.000 977000,6557564,33.078 978000,6564744,33.109 979000,6571924,33.172 980000,6579104,33.172 981000,6586285,33.203 982000,6593466,33.234 983000,6600648,33.312 984000,6607830,33.281 985000,6615012,33.375 986000,6622196,33.422 987000,6629379,33.453 988000,6636563,33.453 989000,6643748,33.516 990000,6650933,33.562 991000,6658118,33.578 992000,6665304,33.641 993000,6672490,33.688 994000,6679677,33.703 995000,6686865,33.750 996000,6694053,33.766 997000,6701241,33.859 998000,6708430,33.859 999000,6715619,33.875 1000000,6722809,33.969