Consider $f \in C^2$. A descent method consists to iteratively compute $$ x_{k+1} = x_k + \alpha^* d_k $$ where $\alpha^*$ approximately minimizes $f(x_k - \alpha d_k)$.
using Optim
using Plots
plotly()
┌ Info: Precompiling Optim [429524aa-4258-5aef-a3af-852621145aeb] └ @ Base loading.jl:1273 WARNING: Method definition vec(Number) in module FiniteDiff at C:\Users\slash\.julia\packages\FiniteDiff\EBys0\src\jacobians.jl:128 overwritten in module DiffEqDiffTools at C:\Users\slash\.julia\packages\DiffEqDiffTools\3mm8U\src\jacobians.jl:114. ** incremental compilation may be fatally broken for this module ** ┌ Info: For saving to png with the Plotly backend ORCA has to be installed. └ @ Plots C:\Users\slash\.julia\packages\Plots\qZHsp\src\backends.jl:363
Plots.PlotlyBackend()
Several linesearch techniques are proposed in Julia, as explained in the page https://github.com/JuliaNLSolvers/LineSearches.jl
Consider again the Rosenbrock example, whose mathematical expression is
Its gradient can be computed as
The minimizer is located at $(1,1)$. Indeed, $$ \nabla f(1,1) = \begin{pmatrix} 0 \\ 0 \end{pmatrix} $$ and $$ \nabla^2 f(1,1) = \begin{pmatrix} 802 & -400 \\ -400 & 200 \end{pmatrix} $$ The determinants of the principal minors are positive as they are respectively 802 and $802\times200-400^2= 400$, so the Hessian is positive definite.
# Rosenbrock function
# Source: https://bitbucket.org/lurk3r/optim.jl
function rosenbrock(x::Vector)
return (1.0 - x[1])^2 + 100.0 * (x[2] - x[1]^2)^2
end
function rosenbrock_gradient!(storage::Vector, x::Vector)
storage[1] = -2.0 * (1.0 - x[1]) - 400.0 * (x[2] - x[1]^2) * x[1]
storage[2] = 200.0 * (x[2] - x[1]^2)
end
function rosenbrock_hessian!(storage::Matrix, x::Vector)
storage[1, 1] = 2.0 - 400.0 * x[2] + 1200.0 * x[1]^2
storage[1, 2] = -400.0 * x[1]
storage[2, 1] = -400.0 * x[1]
storage[2, 2] = 200.0
end
rosenbrock_hessian! (generic function with 1 method)
using Plots
default(size=(600,600), fc=:heat)
x, y = 0:0.02:1.0, 0:0.02:1.0
z = Surface((x,y)->rosenbrock([x,y]), x, y)
surface(x,y,z, linealpha = 0.3)
Plots.contour(x,y,z, linealpha = 0.1, levels=1600)
We can optimize it using the optimize function present in the package optim.jl
res = optimize(rosenbrock, rosenbrock_gradient!,
[20.0, 20.0],
Optim.GradientDescent(),
Optim.Options(g_tol = 1e-6,
store_trace = true,
show_trace = true))
Iter Function value Gradient norm
0 1.444036e+07 3.040038e+06
* time: 0.0
1 2.680958e+06 8.881503e+05
* time: 0.003000020980834961
2 6.986401e+02 4.430920e+03
* time: 0.006999969482421875
3 1.422712e+01 2.423975e+02
* time: 0.020999908447265625
4 1.241984e+01 7.750435e-01
* time: 0.03600001335144043
5 1.241547e+01 1.200614e+01
* time: 0.0409998893737793
6 1.241110e+01 8.544267e-01
* time: 0.04399991035461426
7 1.241103e+01 8.557174e-01
* time: 0.056999921798706055
8 1.241096e+01 8.544292e-01
* time: 0.06999993324279785
9 1.241089e+01 8.557152e-01
* time: 0.09500002861022949
10 1.241081e+01 8.544285e-01
* time: 0.12899994850158691
11 1.241074e+01 8.557130e-01
* time: 0.16000008583068848
12 1.241067e+01 8.544278e-01
* time: 0.18799996376037598
13 1.241060e+01 8.557108e-01
* time: 0.20300006866455078
14 1.241053e+01 8.544272e-01
* time: 0.22799992561340332
15 1.241045e+01 8.557086e-01
* time: 0.24699997901916504
16 1.241038e+01 8.544265e-01
* time: 0.2609999179840088
17 1.241031e+01 8.557064e-01
* time: 0.26399993896484375
18 1.241024e+01 8.544259e-01
* time: 0.2779998779296875
19 1.241016e+01 8.557042e-01
* time: 0.29600000381469727
20 1.241009e+01 8.544252e-01
* time: 0.309999942779541
21 1.241002e+01 8.557020e-01
* time: 0.32399988174438477
22 1.240995e+01 8.544246e-01
* time: 0.3280000686645508
23 1.240987e+01 8.556998e-01
* time: 0.34599995613098145
24 1.240980e+01 8.544239e-01
* time: 0.3510000705718994
25 1.240973e+01 8.556976e-01
* time: 0.36700010299682617
26 1.240966e+01 8.544232e-01
* time: 0.3689999580383301
27 1.240958e+01 8.556955e-01
* time: 0.38299989700317383
28 1.240951e+01 8.544226e-01
* time: 0.38700008392333984
29 1.240944e+01 8.556933e-01
* time: 0.40199995040893555
30 1.240937e+01 8.544219e-01
* time: 0.4049999713897705
31 1.240930e+01 8.556911e-01
* time: 0.4089999198913574
32 1.240922e+01 8.544213e-01
* time: 0.4140000343322754
33 1.240915e+01 8.556889e-01
* time: 0.42100000381469727
34 1.240908e+01 8.544206e-01
* time: 0.4419999122619629
35 1.240901e+01 8.556867e-01
* time: 0.4679999351501465
36 1.240893e+01 8.544199e-01
* time: 0.4830000400543213
37 1.240886e+01 8.556845e-01
* time: 0.4960000514984131
38 1.240879e+01 8.544193e-01
* time: 0.5090000629425049
39 1.240872e+01 8.556823e-01
* time: 0.5130000114440918
40 1.240864e+01 8.544186e-01
* time: 0.5269999504089355
41 1.240857e+01 8.556802e-01
* time: 0.5499999523162842
42 1.240850e+01 8.544180e-01
* time: 0.5539999008178711
43 1.240843e+01 8.556780e-01
* time: 0.5690000057220459
44 1.240835e+01 8.544173e-01
* time: 0.5820000171661377
45 1.240828e+01 8.556758e-01
* time: 0.5980000495910645
46 1.240821e+01 8.544167e-01
* time: 0.6150000095367432
47 1.240814e+01 8.556736e-01
* time: 0.6189999580383301
48 1.240806e+01 8.544160e-01
* time: 0.6329998970031738
49 1.240799e+01 8.556714e-01
* time: 0.6470000743865967
50 1.240792e+01 8.544153e-01
* time: 0.6730000972747803
51 1.240785e+01 8.556693e-01
* time: 0.6779999732971191
52 1.240778e+01 8.544147e-01
* time: 0.6909999847412109
53 1.240770e+01 8.556671e-01
* time: 0.7070000171661377
54 1.240763e+01 8.544140e-01
* time: 0.7109999656677246
55 1.240756e+01 8.556649e-01
* time: 0.7130000591278076
56 1.240749e+01 8.544134e-01
* time: 0.7260000705718994
57 1.240741e+01 8.556627e-01
* time: 0.7330000400543213
58 1.240734e+01 8.544127e-01
* time: 0.747999906539917
59 1.240727e+01 8.556605e-01
* time: 0.75
60 1.240720e+01 8.544120e-01
* time: 0.7630000114440918
61 1.240712e+01 8.556584e-01
* time: 0.7909998893737793
62 1.240705e+01 8.544114e-01
* time: 0.8169999122619629
63 1.240698e+01 8.556562e-01
* time: 0.8310000896453857
64 1.240691e+01 8.544107e-01
* time: 0.8340001106262207
65 1.240683e+01 8.556540e-01
* time: 0.8469998836517334
66 1.240676e+01 8.544101e-01
* time: 0.8910000324249268
67 1.240669e+01 8.556518e-01
* time: 0.9049999713897705
68 1.240662e+01 8.544094e-01
* time: 0.9110000133514404
69 1.240654e+01 8.556497e-01
* time: 0.9259998798370361
70 1.240647e+01 8.544087e-01
* time: 0.9289999008178711
71 1.240640e+01 8.556475e-01
* time: 0.9309999942779541
72 1.240633e+01 8.544081e-01
* time: 0.9600000381469727
73 1.240626e+01 8.556453e-01
* time: 0.9760000705718994
74 1.240618e+01 8.544074e-01
* time: 1.0079998970031738
75 1.240611e+01 8.556432e-01
* time: 1.0409998893737793
76 1.240604e+01 8.544068e-01
* time: 1.059000015258789
77 1.240597e+01 8.556410e-01
* time: 1.065999984741211
78 1.240589e+01 8.544061e-01
* time: 1.0799999237060547
79 1.240582e+01 8.556388e-01
* time: 1.1050000190734863
80 1.240575e+01 8.544054e-01
* time: 1.1319999694824219
81 1.240568e+01 8.556366e-01
* time: 1.1510000228881836
82 1.240560e+01 8.544048e-01
* time: 1.1589999198913574
83 1.240553e+01 8.556345e-01
* time: 1.1630001068115234
84 1.240546e+01 8.544041e-01
* time: 1.1989998817443848
85 1.240539e+01 8.556323e-01
* time: 1.2009999752044678
86 1.240531e+01 8.544035e-01
* time: 1.2279999256134033
87 1.240524e+01 8.556301e-01
* time: 1.250999927520752
88 1.240517e+01 8.544028e-01
* time: 1.253000020980835
89 1.240510e+01 8.556280e-01
* time: 1.2669999599456787
90 1.240502e+01 8.544021e-01
* time: 1.2809998989105225
91 1.240495e+01 8.556258e-01
* time: 1.2999999523162842
92 1.240488e+01 8.544015e-01
* time: 1.3269999027252197
93 1.240481e+01 8.556236e-01
* time: 1.3480000495910645
94 1.240474e+01 8.544008e-01
* time: 1.3650000095367432
95 1.240466e+01 8.556215e-01
* time: 1.371999979019165
96 1.240459e+01 8.544002e-01
* time: 1.378999948501587
97 1.240452e+01 8.556193e-01
* time: 1.4010000228881836
98 1.240445e+01 8.543995e-01
* time: 1.4219999313354492
99 1.240437e+01 8.556172e-01
* time: 1.4259998798370361
100 1.240430e+01 8.543988e-01
* time: 1.4300000667572021
101 1.240423e+01 8.556150e-01
* time: 1.4470000267028809
102 1.240416e+01 8.543982e-01
* time: 1.4830000400543213
103 1.240408e+01 8.556128e-01
* time: 1.5090000629425049
104 1.240401e+01 8.543975e-01
* time: 1.5269999504089355
105 1.240394e+01 8.556107e-01
* time: 1.5469999313354492
106 1.240387e+01 8.543968e-01
* time: 1.561000108718872
107 1.240379e+01 8.556085e-01
* time: 1.5899999141693115
108 1.240372e+01 8.543962e-01
* time: 1.5950000286102295
109 1.240365e+01 8.556063e-01
* time: 1.6129999160766602
110 1.240358e+01 8.543955e-01
* time: 1.6299998760223389
111 1.240350e+01 8.556042e-01
* time: 1.6449999809265137
112 1.240343e+01 8.543949e-01
* time: 1.6500000953674316
113 1.240336e+01 8.556020e-01
* time: 1.6670000553131104
114 1.240329e+01 8.543942e-01
* time: 1.6800000667572021
115 1.240322e+01 8.555999e-01
* time: 1.696000099182129
116 1.240314e+01 8.543935e-01
* time: 1.7119998931884766
117 1.240307e+01 8.555977e-01
* time: 1.7279999256134033
118 1.240300e+01 8.543929e-01
* time: 1.7320001125335693
119 1.240293e+01 8.555956e-01
* time: 1.7609999179840088
120 1.240285e+01 8.543922e-01
* time: 1.7769999504089355
121 1.240278e+01 8.555934e-01
* time: 1.7969999313354492
122 1.240271e+01 8.543915e-01
* time: 1.8029999732971191
123 1.240264e+01 8.555912e-01
* time: 1.816999912261963
124 1.240256e+01 8.543909e-01
* time: 1.8299999237060547
125 1.240249e+01 8.555891e-01
* time: 1.8589999675750732
126 1.240242e+01 8.543902e-01
* time: 1.877000093460083
127 1.240235e+01 8.555869e-01
* time: 1.8970000743865967
128 1.240227e+01 8.543896e-01
* time: 1.9259998798370361
129 1.240220e+01 8.555848e-01
* time: 1.9300000667572021
130 1.240213e+01 8.543889e-01
* time: 1.9719998836517334
131 1.240206e+01 8.555826e-01
* time: 2.007999897003174
132 1.240198e+01 8.543882e-01
* time: 2.0230000019073486
133 1.240191e+01 8.555805e-01
* time: 2.0429999828338623
134 1.240184e+01 8.543876e-01
* time: 2.049999952316284
135 1.240177e+01 8.555783e-01
* time: 2.0859999656677246
136 1.240169e+01 8.543869e-01
* time: 2.131999969482422
137 1.240162e+01 8.555762e-01
* time: 2.1640000343322754
138 1.240155e+01 8.543862e-01
* time: 2.1710000038146973
139 1.240148e+01 8.555740e-01
* time: 2.194999933242798
140 1.240141e+01 8.543856e-01
* time: 2.2130000591278076
141 1.240133e+01 8.555719e-01
* time: 2.239000082015991
142 1.240126e+01 8.543849e-01
* time: 2.246999979019165
143 1.240119e+01 8.555697e-01
* time: 2.265000104904175
144 1.240112e+01 8.543843e-01
* time: 2.2709999084472656
145 1.240104e+01 8.555676e-01
* time: 2.2769999504089355
146 1.240097e+01 8.543836e-01
* time: 2.305999994277954
147 1.240090e+01 8.555654e-01
* time: 2.3269999027252197
148 1.240083e+01 8.543829e-01
* time: 2.3299999237060547
149 1.240075e+01 8.555633e-01
* time: 2.3450000286102295
150 1.240068e+01 8.543823e-01
* time: 2.359999895095825
151 1.240061e+01 8.555611e-01
* time: 2.371999979019165
152 1.240054e+01 8.543816e-01
* time: 2.3889999389648438
153 1.240046e+01 8.555590e-01
* time: 2.3959999084472656
154 1.240039e+01 8.543809e-01
* time: 2.4119999408721924
155 1.240032e+01 8.555569e-01
* time: 2.430000066757202
156 1.240025e+01 8.543803e-01
* time: 2.450000047683716
157 1.240017e+01 8.555547e-01
* time: 2.4630000591278076
158 1.240010e+01 8.543796e-01
* time: 2.4839999675750732
159 1.240003e+01 8.555526e-01
* time: 2.490000009536743
160 1.239996e+01 8.543789e-01
* time: 2.50600004196167
161 1.239988e+01 8.555504e-01
* time: 2.5239999294281006
162 1.239981e+01 8.543783e-01
* time: 2.555000066757202
163 1.239974e+01 8.555483e-01
* time: 2.5759999752044678
164 1.239967e+01 8.543776e-01
* time: 2.5940001010894775
165 1.239960e+01 8.555461e-01
* time: 2.6019999980926514
166 1.239952e+01 8.543769e-01
* time: 2.6110000610351562
167 1.239945e+01 8.555440e-01
* time: 2.615000009536743
168 1.239938e+01 8.543763e-01
* time: 2.6529998779296875
169 1.239931e+01 8.555419e-01
* time: 2.686000108718872
170 1.239923e+01 8.543756e-01
* time: 2.7330000400543213
171 1.239916e+01 8.555397e-01
* time: 2.736999988555908
172 1.239909e+01 8.543750e-01
* time: 2.739000082015991
173 1.239902e+01 8.555376e-01
* time: 2.754999876022339
174 1.239894e+01 8.543743e-01
* time: 2.7709999084472656
175 1.239887e+01 8.555354e-01
* time: 2.7920000553131104
176 1.239880e+01 8.543736e-01
* time: 2.809000015258789
177 1.239873e+01 8.555333e-01
* time: 2.822000026702881
178 1.239865e+01 8.543730e-01
* time: 2.8310000896453857
179 1.239858e+01 8.555312e-01
* time: 2.8459999561309814
180 1.239851e+01 8.543723e-01
* time: 2.8540000915527344
181 1.239844e+01 8.555290e-01
* time: 2.871000051498413
182 1.239836e+01 8.543716e-01
* time: 2.874000072479248
183 1.239829e+01 8.555269e-01
* time: 2.9010000228881836
184 1.239822e+01 8.543710e-01
* time: 2.9159998893737793
185 1.239815e+01 8.555248e-01
* time: 2.934000015258789
186 1.239807e+01 8.543703e-01
* time: 2.937999963760376
187 1.239800e+01 8.555226e-01
* time: 2.944999933242798
188 1.239793e+01 8.543696e-01
* time: 2.9649999141693115
189 1.239786e+01 8.555205e-01
* time: 2.99399995803833
190 1.239779e+01 8.543690e-01
* time: 2.999000072479248
191 1.239771e+01 8.555184e-01
* time: 3.015000104904175
192 1.239764e+01 8.543683e-01
* time: 3.0309998989105225
193 1.239757e+01 8.555162e-01
* time: 3.0460000038146973
194 1.239750e+01 8.543676e-01
* time: 3.062000036239624
195 1.239742e+01 8.555141e-01
* time: 3.0869998931884766
196 1.239735e+01 8.543670e-01
* time: 3.111999988555908
197 1.239728e+01 8.555120e-01
* time: 3.115000009536743
198 1.239721e+01 8.543663e-01
* time: 3.128000020980835
199 1.239713e+01 8.555099e-01
* time: 3.1459999084472656
200 1.239706e+01 8.543656e-01
* time: 3.1649999618530273
201 1.239699e+01 8.555077e-01
* time: 3.190000057220459
202 1.239692e+01 8.543650e-01
* time: 3.194999933242798
203 1.239684e+01 8.555056e-01
* time: 3.2139999866485596
204 1.239677e+01 8.543643e-01
* time: 3.2209999561309814
205 1.239670e+01 8.555035e-01
* time: 3.2239999771118164
206 1.239663e+01 8.543636e-01
* time: 3.2300000190734863
207 1.239655e+01 8.555013e-01
* time: 3.2320001125335693
208 1.239648e+01 8.543630e-01
* time: 3.2360000610351562
209 1.239641e+01 8.554992e-01
* time: 3.239000082015991
210 1.239634e+01 8.543623e-01
* time: 3.2639999389648438
211 1.239626e+01 8.554971e-01
* time: 3.2790000438690186
212 1.239619e+01 8.543616e-01
* time: 3.2939999103546143
213 1.239612e+01 8.554950e-01
* time: 3.296999931335449
214 1.239605e+01 8.543610e-01
* time: 3.322999954223633
215 1.239597e+01 8.554928e-01
* time: 3.3510000705718994
216 1.239590e+01 8.543603e-01
* time: 3.365000009536743
217 1.239583e+01 8.554907e-01
* time: 3.384000062942505
218 1.239576e+01 8.543596e-01
* time: 3.3989999294281006
219 1.239569e+01 8.554886e-01
* time: 3.4059998989105225
220 1.239561e+01 8.543590e-01
* time: 3.4230000972747803
221 1.239554e+01 8.554865e-01
* time: 3.4509999752044678
222 1.239547e+01 8.543583e-01
* time: 3.453000068664551
223 1.239540e+01 8.554843e-01
* time: 3.4570000171661377
224 1.239532e+01 8.543576e-01
* time: 3.4830000400543213
225 1.239525e+01 8.554822e-01
* time: 3.500999927520752
226 1.239518e+01 8.543570e-01
* time: 3.504999876022339
227 1.239511e+01 8.554801e-01
* time: 3.510999917984009
228 1.239503e+01 8.543563e-01
* time: 3.5260000228881836
229 1.239496e+01 8.554780e-01
* time: 3.5429999828338623
230 1.239489e+01 8.543556e-01
* time: 3.5460000038146973
231 1.239482e+01 8.554759e-01
* time: 3.552000045776367
232 1.239474e+01 8.543550e-01
* time: 3.555000066757202
233 1.239467e+01 8.554737e-01
* time: 3.5789999961853027
234 1.239460e+01 8.543543e-01
* time: 3.5950000286102295
235 1.239453e+01 8.554716e-01
* time: 3.624000072479248
236 1.239445e+01 8.543536e-01
* time: 3.6459999084472656
237 1.239438e+01 8.554695e-01
* time: 3.683000087738037
238 1.239431e+01 8.543530e-01
* time: 3.697000026702881
239 1.239424e+01 8.554674e-01
* time: 3.7230000495910645
240 1.239416e+01 8.543523e-01
* time: 3.739000082015991
241 1.239409e+01 8.554653e-01
* time: 3.746000051498413
242 1.239402e+01 8.543516e-01
* time: 3.759000062942505
243 1.239395e+01 8.554632e-01
* time: 3.7850000858306885
244 1.239387e+01 8.543510e-01
* time: 3.8289999961853027
245 1.239380e+01 8.554611e-01
* time: 3.8320000171661377
246 1.239373e+01 8.543503e-01
* time: 3.8559999465942383
247 1.239366e+01 8.554589e-01
* time: 3.8980000019073486
248 1.239359e+01 8.543496e-01
* time: 3.9049999713897705
249 1.239351e+01 8.554568e-01
* time: 3.933000087738037
250 1.239344e+01 8.543490e-01
* time: 3.953000068664551
251 1.239337e+01 8.554547e-01
* time: 3.9560000896453857
252 1.239330e+01 8.543483e-01
* time: 3.9779999256134033
253 1.239322e+01 8.554526e-01
* time: 4.010999917984009
254 1.239315e+01 8.543476e-01
* time: 4.016999959945679
255 1.239308e+01 8.554505e-01
* time: 4.0350000858306885
256 1.239301e+01 8.543470e-01
* time: 4.049999952316284
257 1.239293e+01 8.554484e-01
* time: 4.07699990272522
258 1.239286e+01 8.543463e-01
* time: 4.0899999141693115
259 1.239279e+01 8.554463e-01
* time: 4.107000112533569
260 1.239272e+01 8.543456e-01
* time: 4.127000093460083
261 1.239264e+01 8.554442e-01
* time: 4.144000053405762
262 1.239257e+01 8.543449e-01
* time: 4.1519999504089355
263 1.239250e+01 8.554421e-01
* time: 4.164999961853027
264 1.239243e+01 8.543443e-01
* time: 4.184999942779541
265 1.239235e+01 8.554399e-01
* time: 4.200999975204468
266 1.239228e+01 8.543436e-01
* time: 4.204999923706055
267 1.239221e+01 8.554378e-01
* time: 4.226999998092651
268 1.239214e+01 8.543429e-01
* time: 4.234999895095825
269 1.239206e+01 8.554357e-01
* time: 4.240000009536743
270 1.239199e+01 8.543423e-01
* time: 4.269999980926514
271 1.239192e+01 8.554336e-01
* time: 4.295000076293945
272 1.239185e+01 8.543416e-01
* time: 4.302999973297119
273 1.239177e+01 8.554315e-01
* time: 4.329999923706055
274 1.239170e+01 8.543409e-01
* time: 4.33299994468689
275 1.239163e+01 8.554294e-01
* time: 4.3459999561309814
276 1.239156e+01 8.543403e-01
* time: 4.361000061035156
277 1.239148e+01 8.554273e-01
* time: 4.371999979019165
278 1.239141e+01 8.543396e-01
* time: 4.391000032424927
279 1.239134e+01 8.554252e-01
* time: 4.4019999504089355
280 1.239127e+01 8.543389e-01
* time: 4.4049999713897705
281 1.239120e+01 8.554231e-01
* time: 4.4070000648498535
282 1.239112e+01 8.543383e-01
* time: 4.42300009727478
283 1.239105e+01 8.554210e-01
* time: 4.427000045776367
284 1.239098e+01 8.543376e-01
* time: 4.444999933242798
285 1.239091e+01 8.554189e-01
* time: 4.447999954223633
286 1.239083e+01 8.543369e-01
* time: 4.476000070571899
287 1.239076e+01 8.554168e-01
* time: 4.489000082015991
288 1.239069e+01 8.543362e-01
* time: 4.517999887466431
289 1.239062e+01 8.554147e-01
* time: 4.5329999923706055
290 1.239054e+01 8.543356e-01
* time: 4.549000024795532
291 1.239047e+01 8.554126e-01
* time: 4.565000057220459
292 1.239040e+01 8.543349e-01
* time: 4.629999876022339
293 1.239033e+01 8.554105e-01
* time: 4.661999940872192
294 1.239025e+01 8.543342e-01
* time: 4.680000066757202
295 1.239018e+01 8.554084e-01
* time: 4.697000026702881
296 1.239011e+01 8.543336e-01
* time: 4.703999996185303
297 1.239004e+01 8.554063e-01
* time: 4.760999917984009
298 1.238996e+01 8.543329e-01
* time: 4.7779998779296875
299 1.238989e+01 8.554042e-01
* time: 4.793999910354614
300 1.238982e+01 8.543322e-01
* time: 4.811000108718872
301 1.238975e+01 8.554021e-01
* time: 4.83299994468689
302 1.238967e+01 8.543315e-01
* time: 4.836999893188477
303 1.238960e+01 8.554000e-01
* time: 4.854000091552734
304 1.238953e+01 8.543309e-01
* time: 4.857000112533569
305 1.238946e+01 8.553979e-01
* time: 4.882999897003174
306 1.238938e+01 8.543302e-01
* time: 4.901000022888184
307 1.238931e+01 8.553958e-01
* time: 4.914999961853027
308 1.238924e+01 8.543295e-01
* time: 4.974999904632568
309 1.238917e+01 8.553937e-01
* time: 4.99399995803833
310 1.238909e+01 8.543289e-01
* time: 4.996999979019165
311 1.238902e+01 8.553916e-01
* time: 5.0
312 1.238895e+01 8.543282e-01
* time: 5.0269999504089355
313 1.238888e+01 8.553896e-01
* time: 5.0299999713897705
314 1.238880e+01 8.543275e-01
* time: 5.046000003814697
315 1.238873e+01 8.553875e-01
* time: 5.068000078201294
316 1.238866e+01 8.543269e-01
* time: 5.078999996185303
317 1.238859e+01 8.553854e-01
* time: 5.105000019073486
318 1.238852e+01 8.543262e-01
* time: 5.147000074386597
319 1.238844e+01 8.553833e-01
* time: 5.1519999504089355
320 1.238837e+01 8.543255e-01
* time: 5.190000057220459
321 1.238830e+01 8.553812e-01
* time: 5.196000099182129
322 1.238823e+01 8.543248e-01
* time: 5.200000047683716
323 1.238815e+01 8.553791e-01
* time: 5.203999996185303
324 1.238808e+01 8.543242e-01
* time: 5.226000070571899
325 1.238801e+01 8.553770e-01
* time: 5.247999906539917
326 1.238794e+01 8.543235e-01
* time: 5.421999931335449
327 1.238786e+01 8.553749e-01
* time: 5.427000045776367
328 1.238779e+01 8.543228e-01
* time: 5.453999996185303
329 1.238772e+01 8.553728e-01
* time: 5.51200008392334
330 1.238765e+01 8.543222e-01
* time: 5.555000066757202
331 1.238757e+01 8.553708e-01
* time: 5.568000078201294
332 1.238750e+01 8.543215e-01
* time: 5.572000026702881
333 1.238743e+01 8.553687e-01
* time: 5.585000038146973
334 1.238736e+01 8.543208e-01
* time: 5.604000091552734
335 1.238728e+01 8.553666e-01
* time: 5.618000030517578
336 1.238721e+01 8.543201e-01
* time: 5.632999897003174
337 1.238714e+01 8.553645e-01
* time: 5.650000095367432
338 1.238707e+01 8.543195e-01
* time: 5.664999961853027
339 1.238699e+01 8.553624e-01
* time: 5.690000057220459
340 1.238692e+01 8.543188e-01
* time: 5.746000051498413
341 1.238685e+01 8.553603e-01
* time: 5.7779998779296875
342 1.238678e+01 8.543181e-01
* time: 5.808000087738037
343 1.238670e+01 8.553583e-01
* time: 5.8399999141693115
344 1.238663e+01 8.543174e-01
* time: 5.854000091552734
345 1.238656e+01 8.553562e-01
* time: 5.879999876022339
346 1.238649e+01 8.543168e-01
* time: 5.898000001907349
347 1.238641e+01 8.553541e-01
* time: 5.9029998779296875
348 1.238634e+01 8.543161e-01
* time: 5.9100000858306885
349 1.238627e+01 8.553520e-01
* time: 5.924000024795532
350 1.238620e+01 8.543154e-01
* time: 5.928999900817871
351 1.238612e+01 8.553499e-01
* time: 5.947000026702881
352 1.238605e+01 8.543148e-01
* time: 5.980999946594238
353 1.238598e+01 8.553478e-01
* time: 6.000999927520752
354 1.238591e+01 8.543141e-01
* time: 6.04800009727478
355 1.238583e+01 8.553458e-01
* time: 6.065999984741211
356 1.238576e+01 8.543134e-01
* time: 6.101999998092651
357 1.238569e+01 8.553437e-01
* time: 6.131999969482422
358 1.238562e+01 8.543127e-01
* time: 6.13700008392334
359 1.238555e+01 8.553416e-01
* time: 6.140000104904175
360 1.238547e+01 8.543121e-01
* time: 6.186000108718872
361 1.238540e+01 8.553395e-01
* time: 6.20199990272522
362 1.238533e+01 8.543114e-01
* time: 6.229000091552734
363 1.238526e+01 8.553375e-01
* time: 6.260999917984009
364 1.238518e+01 8.543107e-01
* time: 6.2790000438690186
365 1.238511e+01 8.553354e-01
* time: 6.299000024795532
366 1.238504e+01 8.543100e-01
* time: 6.309000015258789
367 1.238497e+01 8.553333e-01
* time: 6.400000095367432
368 1.238489e+01 8.543094e-01
* time: 6.414999961853027
369 1.238482e+01 8.553312e-01
* time: 6.427999973297119
370 1.238475e+01 8.543087e-01
* time: 6.434999942779541
371 1.238468e+01 8.553292e-01
* time: 6.448999881744385
372 1.238460e+01 8.543080e-01
* time: 6.456000089645386
373 1.238453e+01 8.553271e-01
* time: 6.4709999561309814
374 1.238446e+01 8.543073e-01
* time: 6.49399995803833
375 1.238439e+01 8.553250e-01
* time: 6.500999927520752
376 1.238431e+01 8.543067e-01
* time: 6.552000045776367
377 1.238424e+01 8.553229e-01
* time: 6.575000047683716
378 1.238417e+01 8.543060e-01
* time: 6.5929999351501465
379 1.238410e+01 8.553209e-01
* time: 6.601000070571899
380 1.238402e+01 8.543053e-01
* time: 6.611999988555908
381 1.238395e+01 8.553188e-01
* time: 6.628000020980835
382 1.238388e+01 8.543046e-01
* time: 6.66100001335144
383 1.238381e+01 8.553167e-01
* time: 6.690999984741211
384 1.238373e+01 8.543040e-01
* time: 6.70799994468689
385 1.238366e+01 8.553147e-01
* time: 6.71399998664856
386 1.238359e+01 8.543033e-01
* time: 6.716000080108643
387 1.238352e+01 8.553126e-01
* time: 6.730999946594238
388 1.238344e+01 8.543026e-01
* time: 6.746000051498413
389 1.238337e+01 8.553105e-01
* time: 6.75
390 1.238330e+01 8.543019e-01
* time: 6.767999887466431
391 1.238323e+01 8.553085e-01
* time: 6.773000001907349
392 1.238315e+01 8.543013e-01
* time: 6.812999963760376
393 1.238308e+01 8.553064e-01
* time: 6.828999996185303
394 1.238301e+01 8.543006e-01
* time: 6.851000070571899
395 1.238294e+01 8.553043e-01
* time: 6.869999885559082
396 1.238286e+01 8.542999e-01
* time: 6.900000095367432
397 1.238279e+01 8.553023e-01
* time: 6.9070000648498535
398 1.238272e+01 8.542993e-01
* time: 6.927000045776367
399 1.238265e+01 8.553002e-01
* time: 6.938999891281128
400 1.238257e+01 8.542986e-01
* time: 6.9679999351501465
401 1.238250e+01 8.552981e-01
* time: 7.016000032424927
402 1.238243e+01 8.542979e-01
* time: 7.049000024795532
403 1.238236e+01 8.552961e-01
* time: 7.069999933242798
404 1.238228e+01 8.542972e-01
* time: 7.085000038146973
405 1.238221e+01 8.552940e-01
* time: 7.101000070571899
406 1.238214e+01 8.542965e-01
* time: 7.107000112533569
407 1.238207e+01 8.552919e-01
* time: 7.125
408 1.238199e+01 8.542959e-01
* time: 7.145999908447266
409 1.238192e+01 8.552899e-01
* time: 7.150000095367432
410 1.238185e+01 8.542952e-01
* time: 7.174999952316284
411 1.238178e+01 8.552878e-01
* time: 7.191999912261963
412 1.238171e+01 8.542945e-01
* time: 7.210000038146973
413 1.238163e+01 8.552858e-01
* time: 7.25
414 1.238156e+01 8.542938e-01
* time: 7.299000024795532
415 1.238149e+01 8.552837e-01
* time: 7.315000057220459
416 1.238142e+01 8.542932e-01
* time: 7.318000078201294
417 1.238134e+01 8.552816e-01
* time: 7.352999925613403
418 1.238127e+01 8.542925e-01
* time: 7.367000102996826
419 1.238120e+01 8.552796e-01
* time: 7.395999908447266
420 1.238113e+01 8.542918e-01
* time: 7.41100001335144
421 1.238105e+01 8.552775e-01
* time: 7.447999954223633
422 1.238098e+01 8.542911e-01
* time: 7.4700000286102295
423 1.238091e+01 8.552755e-01
* time: 7.473999977111816
424 1.238084e+01 8.542905e-01
* time: 7.5329999923706055
425 1.238076e+01 8.552734e-01
* time: 7.549999952316284
426 1.238069e+01 8.542898e-01
* time: 7.569999933242798
427 1.238062e+01 8.552714e-01
* time: 7.586999893188477
428 1.238055e+01 8.542891e-01
* time: 7.604000091552734
429 1.238047e+01 8.552693e-01
* time: 7.624000072479248
430 1.238040e+01 8.542884e-01
* time: 7.6559998989105225
431 1.238033e+01 8.552673e-01
* time: 7.664999961853027
432 1.238026e+01 8.542878e-01
* time: 7.671999931335449
433 1.238018e+01 8.552652e-01
* time: 7.684999942779541
434 1.238011e+01 8.542871e-01
* time: 7.691999912261963
435 1.238004e+01 8.552631e-01
* time: 7.726000070571899
436 1.237997e+01 8.542864e-01
* time: 7.763000011444092
437 1.237989e+01 8.552611e-01
* time: 7.835999965667725
438 1.237982e+01 8.542857e-01
* time: 7.933000087738037
439 1.237975e+01 8.552590e-01
* time: 8.03600001335144
440 1.237968e+01 8.542851e-01
* time: 8.128999948501587
441 1.237960e+01 8.552570e-01
* time: 8.183000087738037
442 1.237953e+01 8.542844e-01
* time: 8.259000062942505
443 1.237946e+01 8.552549e-01
* time: 8.325999975204468
444 1.237939e+01 8.542837e-01
* time: 8.446000099182129
445 1.237931e+01 8.552529e-01
* time: 8.503999948501587
446 1.237924e+01 8.542830e-01
* time: 8.563999891281128
447 1.237917e+01 8.552508e-01
* time: 8.615999937057495
448 1.237910e+01 8.542823e-01
* time: 8.63700008392334
449 1.237902e+01 8.552488e-01
* time: 8.677000045776367
450 1.237895e+01 8.542817e-01
* time: 8.717000007629395
451 1.237888e+01 8.552467e-01
* time: 8.73799991607666
452 1.237881e+01 8.542810e-01
* time: 8.747999906539917
453 1.237873e+01 8.552447e-01
* time: 8.76799988746643
454 1.237866e+01 8.542803e-01
* time: 8.775000095367432
455 1.237859e+01 8.552426e-01
* time: 8.789999961853027
456 1.237852e+01 8.542796e-01
* time: 8.799000024795532
457 1.237844e+01 8.552406e-01
* time: 8.809999942779541
458 1.237837e+01 8.542790e-01
* time: 8.82800006866455
459 1.237830e+01 8.552386e-01
* time: 8.845999956130981
460 1.237823e+01 8.542783e-01
* time: 8.879999876022339
461 1.237815e+01 8.552365e-01
* time: 8.897000074386597
462 1.237808e+01 8.542776e-01
* time: 8.90499997138977
463 1.237801e+01 8.552345e-01
* time: 8.924000024795532
464 1.237794e+01 8.542769e-01
* time: 8.940000057220459
465 1.237786e+01 8.552324e-01
* time: 8.946000099182129
466 1.237779e+01 8.542762e-01
* time: 8.95199990272522
467 1.237772e+01 8.552304e-01
* time: 8.967000007629395
468 1.237765e+01 8.542756e-01
* time: 9.003999948501587
469 1.237757e+01 8.552283e-01
* time: 9.006999969482422
470 1.237750e+01 8.542749e-01
* time: 9.022000074386597
471 1.237743e+01 8.552263e-01
* time: 9.036999940872192
472 1.237736e+01 8.542742e-01
* time: 9.05299997329712
473 1.237728e+01 8.552242e-01
* time: 9.109999895095825
474 1.237721e+01 8.542735e-01
* time: 9.117000102996826
475 1.237714e+01 8.552222e-01
* time: 9.147000074386597
476 1.237707e+01 8.542729e-01
* time: 9.154000043869019
477 1.237699e+01 8.552202e-01
* time: 9.170000076293945
478 1.237692e+01 8.542722e-01
* time: 9.210000038146973
479 1.237685e+01 8.552181e-01
* time: 9.216000080108643
480 1.237678e+01 8.542715e-01
* time: 9.249000072479248
481 1.237670e+01 8.552161e-01
* time: 9.280999898910522
482 1.237663e+01 8.542708e-01
* time: 9.300999879837036
483 1.237656e+01 8.552140e-01
* time: 9.32699990272522
484 1.237649e+01 8.542701e-01
* time: 9.369999885559082
485 1.237641e+01 8.552120e-01
* time: 9.394000053405762
486 1.237634e+01 8.542695e-01
* time: 9.42300009727478
487 1.237627e+01 8.552100e-01
* time: 9.431999921798706
488 1.237620e+01 8.542688e-01
* time: 9.469000101089478
489 1.237613e+01 8.552079e-01
* time: 9.4760000705719
490 1.237605e+01 8.542681e-01
* time: 9.48799991607666
491 1.237598e+01 8.552059e-01
* time: 9.51799988746643
492 1.237591e+01 8.542674e-01
* time: 9.53600001335144
493 1.237584e+01 8.552039e-01
* time: 9.57800006866455
494 1.237576e+01 8.542667e-01
* time: 9.588000059127808
495 1.237569e+01 8.552018e-01
* time: 9.611999988555908
496 1.237562e+01 8.542661e-01
* time: 9.63100004196167
497 1.237555e+01 8.551998e-01
* time: 9.69700002670288
498 1.237547e+01 8.542654e-01
* time: 9.700999975204468
499 1.237540e+01 8.551978e-01
* time: 9.70300006866455
500 1.237533e+01 8.542647e-01
* time: 9.747999906539917
501 1.237526e+01 8.551957e-01
* time: 9.782000064849854
502 1.237518e+01 8.542640e-01
* time: 9.789000034332275
503 1.237511e+01 8.551937e-01
* time: 9.816999912261963
504 1.237504e+01 8.542633e-01
* time: 9.829999923706055
505 1.237497e+01 8.551917e-01
* time: 9.877000093460083
506 1.237489e+01 8.542627e-01
* time: 9.901999950408936
507 1.237482e+01 8.551896e-01
* time: 9.928999900817871
508 1.237475e+01 8.542620e-01
* time: 9.98799991607666
509 1.237468e+01 8.551876e-01
* time: 9.99399995803833
510 1.237460e+01 8.542613e-01
* time: 9.997999906539917
511 1.237453e+01 8.551856e-01
* time: 10.016000032424927
512 1.237446e+01 8.542606e-01
* time: 10.035000085830688
513 1.237439e+01 8.551835e-01
* time: 10.043999910354614
514 1.237431e+01 8.542600e-01
* time: 10.050999879837036
515 1.237424e+01 8.551815e-01
* time: 10.127000093460083
516 1.237417e+01 8.542593e-01
* time: 10.158999919891357
517 1.237410e+01 8.551795e-01
* time: 10.175999879837036
518 1.237402e+01 8.542586e-01
* time: 10.178999900817871
519 1.237395e+01 8.551775e-01
* time: 10.210000038146973
520 1.237388e+01 8.542579e-01
* time: 10.223999977111816
521 1.237381e+01 8.551754e-01
* time: 10.285000085830688
522 1.237373e+01 8.542572e-01
* time: 10.286999940872192
523 1.237366e+01 8.551734e-01
* time: 10.300999879837036
524 1.237359e+01 8.542565e-01
* time: 10.313999891281128
525 1.237352e+01 8.551714e-01
* time: 10.33299994468689
526 1.237344e+01 8.542559e-01
* time: 10.349999904632568
527 1.237337e+01 8.551694e-01
* time: 10.365000009536743
528 1.237330e+01 8.542552e-01
* time: 10.36899995803833
529 1.237323e+01 8.551673e-01
* time: 10.395999908447266
530 1.237315e+01 8.542545e-01
* time: 10.402999877929688
531 1.237308e+01 8.551653e-01
* time: 10.405999898910522
532 1.237301e+01 8.542538e-01
* time: 10.421000003814697
533 1.237294e+01 8.551633e-01
* time: 10.42799997329712
534 1.237286e+01 8.542531e-01
* time: 10.441999912261963
535 1.237279e+01 8.551613e-01
* time: 10.470999956130981
536 1.237272e+01 8.542525e-01
* time: 10.48799991607666
537 1.237265e+01 8.551592e-01
* time: 10.515000104904175
538 1.237257e+01 8.542518e-01
* time: 10.520999908447266
539 1.237250e+01 8.551572e-01
* time: 10.562000036239624
540 1.237243e+01 8.542511e-01
* time: 10.591000080108643
541 1.237236e+01 8.551552e-01
* time: 10.621000051498413
542 1.237228e+01 8.542504e-01
* time: 10.641000032424927
543 1.237221e+01 8.551532e-01
* time: 10.644000053405762
544 1.237214e+01 8.542497e-01
* time: 10.650000095367432
545 1.237207e+01 8.551512e-01
* time: 10.664999961853027
546 1.237199e+01 8.542491e-01
* time: 10.67199993133545
547 1.237192e+01 8.551491e-01
* time: 10.687000036239624
548 1.237185e+01 8.542484e-01
* time: 10.704999923706055
549 1.237178e+01 8.551471e-01
* time: 10.7260000705719
550 1.237170e+01 8.542477e-01
* time: 10.739000082015991
551 1.237163e+01 8.551451e-01
* time: 10.776999950408936
552 1.237156e+01 8.542470e-01
* time: 10.806999921798706
553 1.237149e+01 8.551431e-01
* time: 10.836999893188477
554 1.237141e+01 8.542463e-01
* time: 10.852999925613403
555 1.237134e+01 8.551411e-01
* time: 10.868000030517578
556 1.237127e+01 8.542456e-01
* time: 10.872999906539917
557 1.237120e+01 8.551391e-01
* time: 10.890000104904175
558 1.237112e+01 8.542450e-01
* time: 10.894000053405762
559 1.237105e+01 8.551370e-01
* time: 10.936000108718872
560 1.237098e+01 8.542443e-01
* time: 10.953999996185303
561 1.237091e+01 8.551350e-01
* time: 10.980999946594238
562 1.237083e+01 8.542436e-01
* time: 10.994999885559082
563 1.237076e+01 8.551330e-01
* time: 11.013000011444092
564 1.237069e+01 8.542429e-01
* time: 11.027999877929688
565 1.237062e+01 8.551310e-01
* time: 11.03600001335144
566 1.237054e+01 8.542422e-01
* time: 11.049999952316284
567 1.237047e+01 8.551290e-01
* time: 11.053999900817871
568 1.237040e+01 8.542416e-01
* time: 11.058000087738037
569 1.237033e+01 8.551270e-01
* time: 11.075000047683716
570 1.237025e+01 8.542409e-01
* time: 11.081000089645386
571 1.237018e+01 8.551250e-01
* time: 11.086999893188477
572 1.237011e+01 8.542402e-01
* time: 11.091000080108643
573 1.237004e+01 8.551230e-01
* time: 11.092999935150146
574 1.236996e+01 8.542395e-01
* time: 11.11899995803833
575 1.236989e+01 8.551209e-01
* time: 11.157000064849854
576 1.236982e+01 8.542388e-01
* time: 11.177000045776367
577 1.236975e+01 8.551189e-01
* time: 11.20799994468689
578 1.236967e+01 8.542381e-01
* time: 11.229000091552734
579 1.236960e+01 8.551169e-01
* time: 11.23799991607666
580 1.236953e+01 8.542375e-01
* time: 11.24399995803833
581 1.236946e+01 8.551149e-01
* time: 11.257999897003174
582 1.236938e+01 8.542368e-01
* time: 11.272000074386597
583 1.236931e+01 8.551129e-01
* time: 11.289999961853027
584 1.236924e+01 8.542361e-01
* time: 11.305999994277954
585 1.236917e+01 8.551109e-01
* time: 11.328999996185303
586 1.236909e+01 8.542354e-01
* time: 11.33400011062622
587 1.236902e+01 8.551089e-01
* time: 11.335999965667725
588 1.236895e+01 8.542347e-01
* time: 11.341000080108643
589 1.236888e+01 8.551069e-01
* time: 11.35700011253357
590 1.236880e+01 8.542340e-01
* time: 11.367000102996826
591 1.236873e+01 8.551049e-01
* time: 11.369999885559082
592 1.236866e+01 8.542334e-01
* time: 11.382999897003174
593 1.236859e+01 8.551029e-01
* time: 11.401000022888184
594 1.236851e+01 8.542327e-01
* time: 11.405999898910522
595 1.236844e+01 8.551009e-01
* time: 11.427000045776367
596 1.236837e+01 8.542320e-01
* time: 11.444000005722046
597 1.236830e+01 8.550989e-01
* time: 11.45799994468689
598 1.236822e+01 8.542313e-01
* time: 11.480999946594238
599 1.236815e+01 8.550969e-01
* time: 11.499000072479248
600 1.236808e+01 8.542306e-01
* time: 11.526999950408936
601 1.236801e+01 8.550949e-01
* time: 11.529000043869019
602 1.236793e+01 8.542299e-01
* time: 11.57699990272522
603 1.236786e+01 8.550929e-01
* time: 11.592000007629395
604 1.236779e+01 8.542293e-01
* time: 11.605999946594238
605 1.236772e+01 8.550909e-01
* time: 11.617000102996826
606 1.236764e+01 8.542286e-01
* time: 11.644999980926514
607 1.236757e+01 8.550889e-01
* time: 11.664999961853027
608 1.236750e+01 8.542279e-01
* time: 11.67199993133545
609 1.236743e+01 8.550869e-01
* time: 11.677000045776367
610 1.236735e+01 8.542272e-01
* time: 11.681999921798706
611 1.236728e+01 8.550849e-01
* time: 11.686000108718872
612 1.236721e+01 8.542265e-01
* time: 11.70799994468689
613 1.236714e+01 8.550829e-01
* time: 11.746000051498413
614 1.236706e+01 8.542258e-01
* time: 11.753000020980835
615 1.236699e+01 8.550809e-01
* time: 11.759999990463257
616 1.236692e+01 8.542252e-01
* time: 11.765000104904175
617 1.236685e+01 8.550789e-01
* time: 11.76799988746643
618 1.236677e+01 8.542245e-01
* time: 11.802000045776367
619 1.236670e+01 8.550769e-01
* time: 11.849999904632568
620 1.236663e+01 8.542238e-01
* time: 11.871999979019165
621 1.236656e+01 8.550749e-01
* time: 11.890000104904175
622 1.236648e+01 8.542231e-01
* time: 11.894000053405762
623 1.236641e+01 8.550729e-01
* time: 11.91100001335144
624 1.236634e+01 8.542224e-01
* time: 11.934999942779541
625 1.236627e+01 8.550709e-01
* time: 11.963000059127808
626 1.236619e+01 8.542217e-01
* time: 11.977999925613403
627 1.236612e+01 8.550689e-01
* time: 12.016000032424927
628 1.236605e+01 8.542210e-01
* time: 12.04699993133545
629 1.236598e+01 8.550669e-01
* time: 12.062999963760376
630 1.236590e+01 8.542204e-01
* time: 12.079999923706055
631 1.236583e+01 8.550649e-01
* time: 12.08299994468689
632 1.236576e+01 8.542197e-01
* time: 12.098999977111816
633 1.236569e+01 8.550629e-01
* time: 12.102999925613403
634 1.236561e+01 8.542190e-01
* time: 12.10700011253357
635 1.236554e+01 8.550609e-01
* time: 12.127000093460083
636 1.236547e+01 8.542183e-01
* time: 12.144999980926514
637 1.236540e+01 8.550589e-01
* time: 12.157999992370605
638 1.236532e+01 8.542176e-01
* time: 12.187000036239624
639 1.236525e+01 8.550569e-01
* time: 12.191999912261963
640 1.236518e+01 8.542169e-01
* time: 12.194000005722046
641 1.236511e+01 8.550549e-01
* time: 12.19700002670288
642 1.236503e+01 8.542162e-01
* time: 12.214999914169312
643 1.236496e+01 8.550530e-01
* time: 12.25600004196167
644 1.236489e+01 8.542156e-01
* time: 12.26799988746643
645 1.236482e+01 8.550510e-01
* time: 12.283999919891357
646 1.236474e+01 8.542149e-01
* time: 12.316999912261963
647 1.236467e+01 8.550490e-01
* time: 12.345999956130981
648 1.236460e+01 8.542142e-01
* time: 12.36299991607666
649 1.236453e+01 8.550470e-01
* time: 12.382999897003174
650 1.236445e+01 8.542135e-01
* time: 12.41700005531311
651 1.236438e+01 8.550450e-01
* time: 12.440999984741211
652 1.236431e+01 8.542128e-01
* time: 12.460000038146973
653 1.236424e+01 8.550430e-01
* time: 12.473000049591064
654 1.236416e+01 8.542121e-01
* time: 12.500999927520752
655 1.236409e+01 8.550410e-01
* time: 12.509000062942505
656 1.236402e+01 8.542114e-01
* time: 12.526000022888184
657 1.236395e+01 8.550390e-01
* time: 12.573999881744385
658 1.236387e+01 8.542108e-01
* time: 12.598000049591064
659 1.236380e+01 8.550371e-01
* time: 12.624000072479248
660 1.236373e+01 8.542101e-01
* time: 12.65499997138977
661 1.236366e+01 8.550351e-01
* time: 12.668999910354614
662 1.236358e+01 8.542094e-01
* time: 12.711999893188477
663 1.236351e+01 8.550331e-01
* time: 12.7260000705719
664 1.236344e+01 8.542087e-01
* time: 12.75
665 1.236337e+01 8.550311e-01
* time: 12.759000062942505
666 1.236329e+01 8.542080e-01
* time: 12.789999961853027
667 1.236322e+01 8.550291e-01
* time: 12.799999952316284
668 1.236315e+01 8.542073e-01
* time: 12.819000005722046
669 1.236308e+01 8.550271e-01
* time: 12.84500002861023
670 1.236300e+01 8.542066e-01
* time: 12.874000072479248
671 1.236293e+01 8.550252e-01
* time: 12.885999917984009
672 1.236286e+01 8.542060e-01
* time: 12.904000043869019
673 1.236279e+01 8.550232e-01
* time: 12.92199993133545
674 1.236271e+01 8.542053e-01
* time: 12.97000002861023
675 1.236264e+01 8.550212e-01
* time: 13.019999980926514
676 1.236257e+01 8.542046e-01
* time: 13.038000106811523
677 1.236250e+01 8.550192e-01
* time: 13.068000078201294
678 1.236242e+01 8.542039e-01
* time: 13.09500002861023
679 1.236235e+01 8.550172e-01
* time: 13.115999937057495
680 1.236228e+01 8.542032e-01
* time: 13.134999990463257
681 1.236221e+01 8.550153e-01
* time: 13.140000104904175
682 1.236213e+01 8.542025e-01
* time: 13.154000043869019
683 1.236206e+01 8.550133e-01
* time: 13.158999919891357
684 1.236199e+01 8.542018e-01
* time: 13.191999912261963
685 1.236192e+01 8.550113e-01
* time: 13.23799991607666
686 1.236184e+01 8.542011e-01
* time: 13.259000062942505
687 1.236177e+01 8.550093e-01
* time: 13.300999879837036
688 1.236170e+01 8.542005e-01
* time: 13.34500002861023
689 1.236163e+01 8.550073e-01
* time: 13.388999938964844
690 1.236155e+01 8.541998e-01
* time: 13.39299988746643
691 1.236148e+01 8.550054e-01
* time: 13.401999950408936
692 1.236141e+01 8.541991e-01
* time: 13.407000064849854
693 1.236134e+01 8.550034e-01
* time: 13.45799994468689
694 1.236126e+01 8.541984e-01
* time: 13.47000002861023
695 1.236119e+01 8.550014e-01
* time: 13.48799991607666
696 1.236112e+01 8.541977e-01
* time: 13.529000043869019
697 1.236105e+01 8.549994e-01
* time: 13.535000085830688
698 1.236097e+01 8.541970e-01
* time: 13.54200005531311
699 1.236090e+01 8.549975e-01
* time: 13.58899998664856
700 1.236083e+01 8.541963e-01
* time: 13.594000101089478
701 1.236076e+01 8.549955e-01
* time: 13.609999895095825
702 1.236068e+01 8.541956e-01
* time: 13.621999979019165
703 1.236061e+01 8.549935e-01
* time: 13.638999938964844
704 1.236054e+01 8.541950e-01
* time: 13.657999992370605
705 1.236046e+01 8.549916e-01
* time: 13.674000024795532
706 1.236039e+01 8.541943e-01
* time: 13.690999984741211
707 1.236032e+01 8.549896e-01
* time: 13.733000040054321
708 1.236025e+01 8.541936e-01
* time: 13.736999988555908
709 1.236017e+01 8.549876e-01
* time: 13.763000011444092
710 1.236010e+01 8.541929e-01
* time: 13.780999898910522
711 1.236003e+01 8.549856e-01
* time: 13.811000108718872
712 1.235996e+01 8.541922e-01
* time: 13.819000005722046
713 1.235988e+01 8.549837e-01
* time: 13.835000038146973
714 1.235981e+01 8.541915e-01
* time: 13.839999914169312
715 1.235974e+01 8.549817e-01
* time: 13.85700011253357
716 1.235967e+01 8.541908e-01
* time: 13.875
717 1.235959e+01 8.549797e-01
* time: 13.901000022888184
718 1.235952e+01 8.541901e-01
* time: 13.92199993133545
719 1.235945e+01 8.549778e-01
* time: 13.967000007629395
720 1.235938e+01 8.541894e-01
* time: 13.997999906539917
721 1.235930e+01 8.549758e-01
* time: 14.01200008392334
722 1.235923e+01 8.541888e-01
* time: 14.022000074386597
723 1.235916e+01 8.549738e-01
* time: 14.050999879837036
724 1.235909e+01 8.541881e-01
* time: 14.081000089645386
725 1.235901e+01 8.549719e-01
* time: 14.098000049591064
726 1.235894e+01 8.541874e-01
* time: 14.105999946594238
727 1.235887e+01 8.549699e-01
* time: 14.114000082015991
728 1.235880e+01 8.541867e-01
* time: 14.132999897003174
729 1.235872e+01 8.549679e-01
* time: 14.161999940872192
730 1.235865e+01 8.541860e-01
* time: 14.168999910354614
731 1.235858e+01 8.549660e-01
* time: 14.186000108718872
732 1.235851e+01 8.541853e-01
* time: 14.206000089645386
733 1.235843e+01 8.549640e-01
* time: 14.223000049591064
734 1.235836e+01 8.541846e-01
* time: 14.256999969482422
735 1.235829e+01 8.549620e-01
* time: 14.282999992370605
736 1.235822e+01 8.541839e-01
* time: 14.305000066757202
737 1.235814e+01 8.549601e-01
* time: 14.359999895095825
738 1.235807e+01 8.541832e-01
* time: 14.394000053405762
739 1.235800e+01 8.549581e-01
* time: 14.401000022888184
740 1.235793e+01 8.541826e-01
* time: 14.405999898910522
741 1.235785e+01 8.549562e-01
* time: 14.428999900817871
742 1.235778e+01 8.541819e-01
* time: 14.450000047683716
743 1.235771e+01 8.549542e-01
* time: 14.519000053405762
744 1.235764e+01 8.541812e-01
* time: 14.526999950408936
745 1.235756e+01 8.549522e-01
* time: 14.53600001335144
746 1.235749e+01 8.541805e-01
* time: 14.54699993133545
747 1.235742e+01 8.549503e-01
* time: 14.555999994277954
748 1.235735e+01 8.541798e-01
* time: 14.579999923706055
749 1.235727e+01 8.549483e-01
* time: 14.605000019073486
750 1.235720e+01 8.541791e-01
* time: 14.625999927520752
751 1.235713e+01 8.549464e-01
* time: 14.64299988746643
752 1.235706e+01 8.541784e-01
* time: 14.660000085830688
753 1.235698e+01 8.549444e-01
* time: 14.680000066757202
754 1.235691e+01 8.541777e-01
* time: 14.710999965667725
755 1.235684e+01 8.549424e-01
* time: 14.72000002861023
756 1.235677e+01 8.541770e-01
* time: 14.800999879837036
757 1.235669e+01 8.549405e-01
* time: 14.845999956130981
758 1.235662e+01 8.541763e-01
* time: 14.891000032424927
759 1.235655e+01 8.549385e-01
* time: 14.954999923706055
760 1.235648e+01 8.541756e-01
* time: 14.960999965667725
761 1.235640e+01 8.549366e-01
* time: 14.9760000705719
762 1.235633e+01 8.541750e-01
* time: 14.980000019073486
763 1.235626e+01 8.549346e-01
* time: 15.00600004196167
764 1.235619e+01 8.541743e-01
* time: 15.009999990463257
765 1.235611e+01 8.549327e-01
* time: 15.01799988746643
766 1.235604e+01 8.541736e-01
* time: 15.035000085830688
767 1.235597e+01 8.549307e-01
* time: 15.05299997329712
768 1.235590e+01 8.541729e-01
* time: 15.075000047683716
769 1.235582e+01 8.549288e-01
* time: 15.094000101089478
770 1.235575e+01 8.541722e-01
* time: 15.108999967575073
771 1.235568e+01 8.549268e-01
* time: 15.125
772 1.235561e+01 8.541715e-01
* time: 15.152999877929688
773 1.235553e+01 8.549249e-01
* time: 15.20300006866455
774 1.235546e+01 8.541708e-01
* time: 15.2260000705719
775 1.235539e+01 8.549229e-01
* time: 15.246000051498413
776 1.235532e+01 8.541701e-01
* time: 15.26799988746643
777 1.235524e+01 8.549210e-01
* time: 15.283999919891357
778 1.235517e+01 8.541694e-01
* time: 15.335999965667725
779 1.235510e+01 8.549190e-01
* time: 15.371000051498413
780 1.235502e+01 8.541687e-01
* time: 15.39299988746643
781 1.235495e+01 8.549171e-01
* time: 15.401000022888184
782 1.235488e+01 8.541680e-01
* time: 15.41599988937378
783 1.235481e+01 8.549151e-01
* time: 15.437999963760376
784 1.235473e+01 8.541674e-01
* time: 15.448999881744385
785 1.235466e+01 8.549132e-01
* time: 15.483999967575073
786 1.235459e+01 8.541667e-01
* time: 15.503999948501587
787 1.235452e+01 8.549112e-01
* time: 15.523000001907349
788 1.235444e+01 8.541660e-01
* time: 15.55299997329712
789 1.235437e+01 8.549093e-01
* time: 15.575000047683716
790 1.235430e+01 8.541653e-01
* time: 15.605000019073486
791 1.235423e+01 8.549073e-01
* time: 15.628000020980835
792 1.235415e+01 8.541646e-01
* time: 15.647000074386597
793 1.235408e+01 8.549054e-01
* time: 15.66599988937378
794 1.235401e+01 8.541639e-01
* time: 15.694000005722046
795 1.235394e+01 8.549034e-01
* time: 15.70199990272522
796 1.235386e+01 8.541632e-01
* time: 15.7260000705719
797 1.235379e+01 8.549015e-01
* time: 15.730000019073486
798 1.235372e+01 8.541625e-01
* time: 15.747999906539917
799 1.235365e+01 8.548995e-01
* time: 15.780999898910522
800 1.235357e+01 8.541618e-01
* time: 15.829999923706055
801 1.235350e+01 8.548976e-01
* time: 15.849999904632568
802 1.235343e+01 8.541611e-01
* time: 15.855999946594238
803 1.235336e+01 8.548956e-01
* time: 15.861000061035156
804 1.235328e+01 8.541604e-01
* time: 15.865999937057495
805 1.235321e+01 8.548937e-01
* time: 15.885999917984009
806 1.235314e+01 8.541597e-01
* time: 15.895999908447266
807 1.235307e+01 8.548918e-01
* time: 15.911999940872192
808 1.235299e+01 8.541591e-01
* time: 15.925999879837036
809 1.235292e+01 8.548898e-01
* time: 15.944999933242798
810 1.235285e+01 8.541584e-01
* time: 15.9760000705719
811 1.235278e+01 8.548879e-01
* time: 16.043999910354614
812 1.235270e+01 8.541577e-01
* time: 16.04800009727478
813 1.235263e+01 8.548859e-01
* time: 16.075000047683716
814 1.235256e+01 8.541570e-01
* time: 16.079999923706055
815 1.235249e+01 8.548840e-01
* time: 16.111000061035156
816 1.235241e+01 8.541563e-01
* time: 16.125999927520752
817 1.235234e+01 8.548821e-01
* time: 16.12999987602234
818 1.235227e+01 8.541556e-01
* time: 16.151999950408936
819 1.235220e+01 8.548801e-01
* time: 16.16700005531311
820 1.235212e+01 8.541549e-01
* time: 16.194000005722046
821 1.235205e+01 8.548782e-01
* time: 16.210999965667725
822 1.235198e+01 8.541542e-01
* time: 16.236999988555908
823 1.235191e+01 8.548762e-01
* time: 16.242000102996826
824 1.235183e+01 8.541535e-01
* time: 16.26699995994568
825 1.235176e+01 8.548743e-01
* time: 16.312000036239624
826 1.235169e+01 8.541528e-01
* time: 16.32699990272522
827 1.235162e+01 8.548724e-01
* time: 16.329999923706055
828 1.235154e+01 8.541521e-01
* time: 16.3510000705719
829 1.235147e+01 8.548704e-01
* time: 16.35599994659424
830 1.235140e+01 8.541514e-01
* time: 16.368000030517578
831 1.235132e+01 8.548685e-01
* time: 16.378000020980835
832 1.235125e+01 8.541507e-01
* time: 16.40400004386902
833 1.235118e+01 8.548666e-01
* time: 16.408999919891357
834 1.235111e+01 8.541500e-01
* time: 16.414999961853027
835 1.235103e+01 8.548646e-01
* time: 16.437999963760376
836 1.235096e+01 8.541493e-01
* time: 16.456000089645386
837 1.235089e+01 8.548627e-01
* time: 16.473000049591064
838 1.235082e+01 8.541487e-01
* time: 16.49399995803833
839 1.235074e+01 8.548608e-01
* time: 16.513000011444092
840 1.235067e+01 8.541480e-01
* time: 16.542999982833862
841 1.235060e+01 8.548588e-01
* time: 16.57100009918213
842 1.235053e+01 8.541473e-01
* time: 16.588000059127808
843 1.235045e+01 8.548569e-01
* time: 16.59500002861023
844 1.235038e+01 8.541466e-01
* time: 16.61400008201599
845 1.235031e+01 8.548550e-01
* time: 16.621000051498413
846 1.235024e+01 8.541459e-01
* time: 16.628000020980835
847 1.235016e+01 8.548530e-01
* time: 16.632999897003174
848 1.235009e+01 8.541452e-01
* time: 16.66599988937378
849 1.235002e+01 8.548511e-01
* time: 16.691999912261963
850 1.234995e+01 8.541445e-01
* time: 16.710000038146973
851 1.234987e+01 8.548492e-01
* time: 16.717000007629395
852 1.234980e+01 8.541438e-01
* time: 16.73300004005432
853 1.234973e+01 8.548472e-01
* time: 16.763000011444092
854 1.234966e+01 8.541431e-01
* time: 16.793999910354614
855 1.234958e+01 8.548453e-01
* time: 16.79800009727478
856 1.234951e+01 8.541424e-01
* time: 16.81500005722046
857 1.234944e+01 8.548434e-01
* time: 16.82100009918213
858 1.234937e+01 8.541417e-01
* time: 16.865000009536743
859 1.234929e+01 8.548415e-01
* time: 16.89299988746643
860 1.234922e+01 8.541410e-01
* time: 16.91100001335144
861 1.234915e+01 8.548395e-01
* time: 16.941999912261963
862 1.234908e+01 8.541403e-01
* time: 16.963000059127808
863 1.234900e+01 8.548376e-01
* time: 16.996999979019165
864 1.234893e+01 8.541396e-01
* time: 17.01699995994568
865 1.234886e+01 8.548357e-01
* time: 17.027999877929688
866 1.234879e+01 8.541389e-01
* time: 17.03600001335144
867 1.234871e+01 8.548338e-01
* time: 17.061000108718872
868 1.234864e+01 8.541382e-01
* time: 17.063999891281128
869 1.234857e+01 8.548318e-01
* time: 17.108999967575073
870 1.234850e+01 8.541375e-01
* time: 17.13599991798401
871 1.234842e+01 8.548299e-01
* time: 17.141000032424927
872 1.234835e+01 8.541368e-01
* time: 17.1489999294281
873 1.234828e+01 8.548280e-01
* time: 17.16700005531311
874 1.234820e+01 8.541362e-01
* time: 17.194000005722046
875 1.234813e+01 8.548261e-01
* time: 17.2260000705719
876 1.234806e+01 8.541355e-01
* time: 17.246000051498413
877 1.234799e+01 8.548241e-01
* time: 17.25
878 1.234791e+01 8.541348e-01
* time: 17.276000022888184
879 1.234784e+01 8.548222e-01
* time: 17.29699993133545
880 1.234777e+01 8.541341e-01
* time: 17.311000108718872
881 1.234770e+01 8.548203e-01
* time: 17.32800006866455
882 1.234762e+01 8.541334e-01
* time: 17.34500002861023
883 1.234755e+01 8.548184e-01
* time: 17.358999967575073
884 1.234748e+01 8.541327e-01
* time: 17.3989999294281
885 1.234741e+01 8.548164e-01
* time: 17.40400004386902
886 1.234733e+01 8.541320e-01
* time: 17.438999891281128
887 1.234726e+01 8.548145e-01
* time: 17.47099995613098
888 1.234719e+01 8.541313e-01
* time: 17.494999885559082
889 1.234712e+01 8.548126e-01
* time: 17.509999990463257
890 1.234704e+01 8.541306e-01
* time: 17.57100009918213
891 1.234697e+01 8.548107e-01
* time: 17.585000038146973
892 1.234690e+01 8.541299e-01
* time: 17.594000101089478
893 1.234683e+01 8.548088e-01
* time: 17.619999885559082
894 1.234675e+01 8.541292e-01
* time: 17.6489999294281
895 1.234668e+01 8.548069e-01
* time: 17.687000036239624
896 1.234661e+01 8.541285e-01
* time: 17.716000080108643
897 1.234654e+01 8.548049e-01
* time: 17.7260000705719
898 1.234646e+01 8.541278e-01
* time: 17.74399995803833
899 1.234639e+01 8.548030e-01
* time: 17.765000104904175
900 1.234632e+01 8.541271e-01
* time: 17.788000106811523
901 1.234625e+01 8.548011e-01
* time: 17.812999963760376
902 1.234617e+01 8.541264e-01
* time: 17.831000089645386
903 1.234610e+01 8.547992e-01
* time: 17.846999883651733
904 1.234603e+01 8.541257e-01
* time: 17.859999895095825
905 1.234596e+01 8.547973e-01
* time: 17.875999927520752
906 1.234588e+01 8.541250e-01
* time: 17.902999877929688
907 1.234581e+01 8.547954e-01
* time: 17.927000045776367
908 1.234574e+01 8.541243e-01
* time: 17.930999994277954
909 1.234567e+01 8.547934e-01
* time: 17.94700002670288
910 1.234559e+01 8.541236e-01
* time: 17.95900011062622
911 1.234552e+01 8.547915e-01
* time: 17.9760000705719
912 1.234545e+01 8.541229e-01
* time: 17.980000019073486
913 1.234537e+01 8.547896e-01
* time: 18.003999948501587
914 1.234530e+01 8.541222e-01
* time: 18.032000064849854
915 1.234523e+01 8.547877e-01
* time: 18.04800009727478
916 1.234516e+01 8.541215e-01
* time: 18.056999921798706
917 1.234508e+01 8.547858e-01
* time: 18.08400011062622
918 1.234501e+01 8.541208e-01
* time: 18.109999895095825
919 1.234494e+01 8.547839e-01
* time: 18.115999937057495
920 1.234487e+01 8.541201e-01
* time: 18.121000051498413
921 1.234479e+01 8.547820e-01
* time: 18.128999948501587
922 1.234472e+01 8.541194e-01
* time: 18.145999908447266
923 1.234465e+01 8.547801e-01
* time: 18.161999940872192
924 1.234458e+01 8.541187e-01
* time: 18.17899990081787
925 1.234450e+01 8.547782e-01
* time: 18.197999954223633
926 1.234443e+01 8.541181e-01
* time: 18.216000080108643
927 1.234436e+01 8.547762e-01
* time: 18.223000049591064
928 1.234429e+01 8.541174e-01
* time: 18.23900008201599
929 1.234421e+01 8.547743e-01
* time: 18.26200008392334
930 1.234414e+01 8.541167e-01
* time: 18.27900004386902
931 1.234407e+01 8.547724e-01
* time: 18.296000003814697
932 1.234400e+01 8.541160e-01
* time: 18.299999952316284
933 1.234392e+01 8.547705e-01
* time: 18.332000017166138
934 1.234385e+01 8.541153e-01
* time: 18.346999883651733
935 1.234378e+01 8.547686e-01
* time: 18.365999937057495
936 1.234371e+01 8.541146e-01
* time: 18.38100004196167
937 1.234363e+01 8.547667e-01
* time: 18.405999898910522
938 1.234356e+01 8.541139e-01
* time: 18.41100001335144
939 1.234349e+01 8.547648e-01
* time: 18.430000066757202
940 1.234342e+01 8.541132e-01
* time: 18.44700002670288
941 1.234334e+01 8.547629e-01
* time: 18.46499991416931
942 1.234327e+01 8.541125e-01
* time: 18.483999967575073
943 1.234320e+01 8.547610e-01
* time: 18.520999908447266
944 1.234312e+01 8.541118e-01
* time: 18.543999910354614
945 1.234305e+01 8.547591e-01
* time: 18.563999891281128
946 1.234298e+01 8.541111e-01
* time: 18.6010000705719
947 1.234291e+01 8.547572e-01
* time: 18.63700008392334
948 1.234283e+01 8.541104e-01
* time: 18.67199993133545
949 1.234276e+01 8.547553e-01
* time: 18.688999891281128
950 1.234269e+01 8.541097e-01
* time: 18.694999933242798
951 1.234262e+01 8.547534e-01
* time: 18.698999881744385
952 1.234254e+01 8.541090e-01
* time: 18.717000007629395
953 1.234247e+01 8.547515e-01
* time: 18.73300004005432
954 1.234240e+01 8.541083e-01
* time: 18.752000093460083
955 1.234233e+01 8.547496e-01
* time: 18.77500009536743
956 1.234225e+01 8.541076e-01
* time: 18.795000076293945
957 1.234218e+01 8.547477e-01
* time: 18.812999963760376
958 1.234211e+01 8.541069e-01
* time: 18.841000080108643
959 1.234204e+01 8.547458e-01
* time: 18.84999990463257
960 1.234196e+01 8.541062e-01
* time: 18.86400008201599
961 1.234189e+01 8.547439e-01
* time: 18.871999979019165
962 1.234182e+01 8.541055e-01
* time: 18.89299988746643
963 1.234175e+01 8.547420e-01
* time: 18.907999992370605
964 1.234167e+01 8.541048e-01
* time: 18.913000106811523
965 1.234160e+01 8.547401e-01
* time: 18.92799997329712
966 1.234153e+01 8.541041e-01
* time: 18.93499994277954
967 1.234146e+01 8.547382e-01
* time: 18.95799994468689
968 1.234138e+01 8.541034e-01
* time: 18.996000051498413
969 1.234131e+01 8.547363e-01
* time: 19.02900004386902
970 1.234124e+01 8.541027e-01
* time: 19.033999919891357
971 1.234117e+01 8.547344e-01
* time: 19.075999975204468
972 1.234109e+01 8.541020e-01
* time: 19.085000038146973
973 1.234102e+01 8.547325e-01
* time: 19.09599995613098
974 1.234095e+01 8.541013e-01
* time: 19.125
975 1.234087e+01 8.547306e-01
* time: 19.1489999294281
976 1.234080e+01 8.541006e-01
* time: 19.163000106811523
977 1.234073e+01 8.547287e-01
* time: 19.174999952316284
978 1.234066e+01 8.540999e-01
* time: 19.194999933242798
979 1.234058e+01 8.547268e-01
* time: 19.210999965667725
980 1.234051e+01 8.540992e-01
* time: 19.227999925613403
981 1.234044e+01 8.547249e-01
* time: 19.259999990463257
982 1.234037e+01 8.540985e-01
* time: 19.35199999809265
983 1.234029e+01 8.547230e-01
* time: 19.37999987602234
984 1.234022e+01 8.540978e-01
* time: 19.388999938964844
985 1.234015e+01 8.547211e-01
* time: 19.39800000190735
986 1.234008e+01 8.540971e-01
* time: 19.40499997138977
987 1.234000e+01 8.547192e-01
* time: 19.430999994277954
988 1.233993e+01 8.540964e-01
* time: 19.448999881744385
989 1.233986e+01 8.547173e-01
* time: 19.47499990463257
990 1.233979e+01 8.540957e-01
* time: 19.506999969482422
991 1.233971e+01 8.547155e-01
* time: 19.538000106811523
992 1.233964e+01 8.540950e-01
* time: 19.57100009918213
993 1.233957e+01 8.547136e-01
* time: 19.59999990463257
994 1.233950e+01 8.540943e-01
* time: 19.608999967575073
995 1.233942e+01 8.547117e-01
* time: 19.628999948501587
996 1.233935e+01 8.540936e-01
* time: 19.634000062942505
997 1.233928e+01 8.547098e-01
* time: 19.657999992370605
998 1.233921e+01 8.540929e-01
* time: 19.661999940872192
999 1.233913e+01 8.547079e-01
* time: 19.66700005531311
1000 1.233906e+01 8.540922e-01
* time: 19.67300009727478
* Status: failure (reached maximum number of iterations) (line search failed)
* Candidate solution
Minimizer: [4.51e+00, 2.04e+01]
Minimum: 1.233906e+01
* Found with
Algorithm: Gradient Descent
Initial Point: [2.00e+01, 2.00e+01]
* Convergence measures
|x - x'| = 1.04e-04 ≰ 0.0e+00
|x - x'|/|x'| = 5.09e-06 ≰ 0.0e+00
|f(x) - f(x')| = 7.26e-05 ≰ 0.0e+00
|f(x) - f(x')|/|f(x')| = 5.88e-06 ≰ 0.0e+00
|g(x)| = 8.54e-01 ≰ 1.0e-06
* Work counters
Seconds run: 20 (vs limit Inf)
Iterations: 1000
f(x) calls: 2506
∇f(x) calls: 2506
res = optimize(rosenbrock, rosenbrock_gradient!,
[20.0, 20.0],
Optim.BFGS(),
Optim.Options(g_tol = 1e-6,
store_trace = true,
show_trace = true))
Iter Function value Gradient norm
0 1.444036e+07 3.040038e+06
* time: 0.0
1 2.680958e+06 8.881503e+05
* time: 0.014999866485595703
2 6.650571e+05 5.858550e+05
* time: 0.01699995994567871
3 2.806304e+02 7.167345e+02
* time: 0.03399991989135742
4 2.794972e+02 3.772877e+01
* time: 0.04799985885620117
5 2.694629e+02 8.824642e+02
* time: 0.06099987030029297
6 2.679257e+02 1.073784e+03
* time: 0.07499980926513672
7 2.615432e+02 1.595776e+03
* time: 0.11699986457824707
8 2.480323e+02 1.178047e+03
* time: 0.12099981307983398
9 2.411404e+02 6.281265e+02
* time: 0.12599992752075195
10 2.318473e+02 2.328093e+02
* time: 0.14699983596801758
11 2.293179e+02 7.429504e+02
* time: 0.18599987030029297
12 2.271862e+02 1.282135e+03
* time: 0.20199990272521973
13 2.195866e+02 1.511525e+03
* time: 0.2089998722076416
14 1.916722e+02 1.049794e+03
* time: 0.2369999885559082
15 1.852938e+02 2.678043e+02
* time: 0.24699997901916504
16 1.824770e+02 2.257172e+02
* time: 0.25999999046325684
17 1.807223e+02 7.043838e+02
* time: 0.2890000343322754
18 1.791228e+02 1.041848e+03
* time: 0.3399999141693115
19 1.745125e+02 1.176254e+03
* time: 0.35500001907348633
20 1.623655e+02 5.553827e+02
* time: 0.35899996757507324
21 1.575354e+02 1.047299e+03
* time: 0.372999906539917
22 1.438367e+02 7.248901e+02
* time: 0.3859999179840088
23 1.415012e+02 7.714994e+01
* time: 0.4010000228881836
24 1.361534e+02 2.564028e+02
* time: 0.4199998378753662
25 1.343146e+02 4.888679e+02
* time: 0.43599987030029297
26 1.322873e+02 7.347831e+02
* time: 0.46000003814697266
27 1.292766e+02 9.784481e+02
* time: 0.4629998207092285
28 1.175307e+02 6.237382e+02
* time: 0.46700000762939453
29 1.147999e+02 1.772825e+02
* time: 0.48599982261657715
30 1.085562e+02 5.876452e+02
* time: 0.49000000953674316
31 1.068158e+02 8.555388e+02
* time: 0.5089998245239258
32 9.705503e+01 2.918149e+02
* time: 0.5130000114440918
33 9.558728e+01 4.672275e+02
* time: 0.5269999504089355
34 9.221983e+01 5.120251e+02
* time: 0.5439999103546143
35 8.630421e+01 5.578439e+02
* time: 0.556999921798706
36 7.417278e+01 4.884472e+02
* time: 0.5639998912811279
37 7.030566e+01 8.957325e+01
* time: 0.5779998302459717
38 6.917628e+01 7.484095e+01
* time: 0.5929999351501465
39 6.812603e+01 2.930674e+02
* time: 0.6329998970031738
40 6.744612e+01 4.813804e+02
* time: 0.6469998359680176
41 6.395227e+01 5.974543e+02
* time: 0.6949999332427979
42 6.268214e+01 1.017006e+03
* time: 0.7259998321533203
43 4.940524e+01 2.791254e+02
* time: 0.7289998531341553
44 4.851947e+01 5.691400e+02
* time: 0.7439999580383301
45 4.687109e+01 1.641540e+02
* time: 0.7730000019073486
46 4.613982e+01 3.026013e+02
* time: 0.7909998893737793
47 4.503657e+01 3.916941e+02
* time: 0.8369998931884766
48 4.208788e+01 3.507581e+02
* time: 0.8550000190734863
49 3.174450e+01 1.637115e+01
* time: 0.8589999675750732
50 3.163005e+01 1.074344e+01
* time: 0.871999979019165
51 3.035454e+01 2.248662e+02
* time: 0.8969998359680176
52 2.918640e+01 2.716024e+02
* time: 0.8989999294281006
53 2.578441e+01 1.306074e+02
* time: 0.9019999504089355
54 2.451655e+01 2.335716e+02
* time: 0.9140000343322754
55 2.097330e+01 2.137949e+02
* time: 0.9279999732971191
56 1.996443e+01 9.432586e+00
* time: 0.9459998607635498
57 1.817363e+01 1.501186e+02
* time: 0.9499998092651367
58 1.762039e+01 2.070211e+02
* time: 0.9629998207092285
59 1.499259e+01 8.796077e+01
* time: 0.9879999160766602
60 1.415933e+01 1.589558e+02
* time: 1.0299999713897705
61 1.180057e+01 1.263296e+02
* time: 1.0439999103546143
62 1.121505e+01 9.872709e+00
* time: 1.0699999332427979
63 1.004045e+01 7.453352e+01
* time: 1.0950000286102295
64 9.867001e+00 9.258542e+01
* time: 1.120999813079834
65 9.164464e+00 1.310284e+02
* time: 1.1419999599456787
66 6.463125e+00 5.063399e+01
* time: 1.1689999103546143
67 6.197393e+00 2.385676e+01
* time: 1.1979999542236328
68 5.275474e+00 5.975018e+01
* time: 1.2139999866485596
69 5.102342e+00 8.160447e+01
* time: 1.2170000076293945
70 4.153169e+00 4.821250e+01
* time: 1.2319998741149902
71 3.342622e+00 1.678964e+01
* time: 1.244999885559082
72 3.296727e+00 2.268162e+01
* time: 1.2809998989105225
73 3.091420e+00 2.716177e+01
* time: 1.2960000038146973
74 2.903246e+00 3.176082e+01
* time: 1.312000036239624
75 2.638841e+00 3.872453e+01
* time: 1.315999984741211
76 2.267693e+00 5.239069e+01
* time: 1.319000005722046
77 1.963828e+00 7.214768e+01
* time: 1.3359999656677246
78 7.782322e-01 3.728406e+00
* time: 1.3609998226165771
79 7.607595e-01 9.788744e+00
* time: 1.366999864578247
80 7.315736e-01 1.750990e+01
* time: 1.375
81 6.551173e-01 2.234978e+01
* time: 1.4040000438690186
82 4.444449e-01 1.537023e+01
* time: 1.4229998588562012
83 3.514617e-01 7.557805e+00
* time: 1.428999900817871
84 2.247160e-01 7.153232e+00
* time: 1.444000005722046
85 2.115741e-01 9.854675e+00
* time: 1.4619998931884766
86 1.589652e-01 9.905336e+00
* time: 1.4800000190734863
87 5.498147e-02 1.425524e+00
* time: 1.4839999675750732
88 4.919028e-02 3.049777e+00
* time: 1.498999834060669
89 3.177471e-02 4.837723e+00
* time: 1.503000020980835
90 5.392510e-04 6.955001e-01
* time: 1.5299999713897705
91 1.076257e-04 1.165555e-01
* time: 1.5339999198913574
92 3.683156e-05 1.419881e-01
* time: 1.5349998474121094
93 7.641772e-07 3.009222e-02
* time: 1.5409998893737793
94 2.553693e-11 8.507457e-05
* time: 1.5449998378753662
95 8.109975e-17 3.265151e-07
* time: 1.5729999542236328
* Status: success
* Candidate solution
Minimizer: [1.00e+00, 1.00e+00]
Minimum: 8.109975e-17
* Found with
Algorithm: BFGS
Initial Point: [2.00e+01, 2.00e+01]
* Convergence measures
|x - x'| = 9.19e-06 ≰ 0.0e+00
|x - x'|/|x'| = 9.19e-06 ≰ 0.0e+00
|f(x) - f(x')| = 2.55e-11 ≰ 0.0e+00
|f(x) - f(x')|/|f(x')| = 3.15e+05 ≰ 0.0e+00
|g(x)| = 3.27e-07 ≤ 1.0e-06
* Work counters
Seconds run: 2 (vs limit Inf)
Iterations: 95
f(x) calls: 284
∇f(x) calls: 284
using BenchmarkTools
@btime res = optimize(rosenbrock, rosenbrock_gradient!,
[0.0, 0.0], Optim.BFGS(),
Optim.Options(g_tol = 1e-6,
store_trace = true,
show_trace = false))
36.800 μs (558 allocations: 29.64 KiB)
* Status: success
* Candidate solution
Minimizer: [1.00e+00, 1.00e+00]
Minimum: 7.645563e-21
* Found with
Algorithm: BFGS
Initial Point: [0.00e+00, 0.00e+00]
* Convergence measures
|x - x'| = 3.48e-07 ≰ 0.0e+00
|x - x'|/|x'| = 3.48e-07 ≰ 0.0e+00
|f(x) - f(x')| = 6.91e-14 ≰ 0.0e+00
|f(x) - f(x')|/|f(x')| = 9.03e+06 ≰ 0.0e+00
|g(x)| = 2.32e-09 ≤ 1.0e-06
* Work counters
Seconds run: 0 (vs limit Inf)
Iterations: 16
f(x) calls: 53
∇f(x) calls: 53
iter = Optim.trace(res)
96-element Array{OptimizationState{Float64,BFGS{LineSearches.InitialStatic{Float64},LineSearches.HagerZhang{Float64,Base.RefValue{Bool}},Nothing,Nothing,Flat}},1}:
0 1.444036e+07 3.040038e+06
* time: 0.0
1 2.680958e+06 8.881503e+05
* time: 0.014999866485595703
2 6.650571e+05 5.858550e+05
* time: 0.01699995994567871
3 2.806304e+02 7.167345e+02
* time: 0.03399991989135742
4 2.794972e+02 3.772877e+01
* time: 0.04799985885620117
5 2.694629e+02 8.824642e+02
* time: 0.06099987030029297
6 2.679257e+02 1.073784e+03
* time: 0.07499980926513672
7 2.615432e+02 1.595776e+03
* time: 0.11699986457824707
8 2.480323e+02 1.178047e+03
* time: 0.12099981307983398
9 2.411404e+02 6.281265e+02
* time: 0.12599992752075195
10 2.318473e+02 2.328093e+02
* time: 0.14699983596801758
11 2.293179e+02 7.429504e+02
* time: 0.18599987030029297
12 2.271862e+02 1.282135e+03
* time: 0.20199990272521973
⋮
84 2.247160e-01 7.153232e+00
* time: 1.444000005722046
85 2.115741e-01 9.854675e+00
* time: 1.4619998931884766
86 1.589652e-01 9.905336e+00
* time: 1.4800000190734863
87 5.498147e-02 1.425524e+00
* time: 1.4839999675750732
88 4.919028e-02 3.049777e+00
* time: 1.498999834060669
89 3.177471e-02 4.837723e+00
* time: 1.503000020980835
90 5.392510e-04 6.955001e-01
* time: 1.5299999713897705
91 1.076257e-04 1.165555e-01
* time: 1.5339999198913574
92 3.683156e-05 1.419881e-01
* time: 1.5349998474121094
93 7.641772e-07 3.009222e-02
* time: 1.5409998893737793
94 2.553693e-11 8.507457e-05
* time: 1.5449998378753662
95 8.109975e-17 3.265151e-07
* time: 1.5729999542236328
Computing gradient and Hessian of complicated, and even sometimes simple, functions can be tedious. In order to alleviate this burden, it is possible to use numerical derivates or automatic differentiation.
Numerical derivatives function are provided in the package Calculus, as illustrated below.
using Calculus, LinearAlgebra
rg = Calculus.gradient(rosenbrock)
#2 (generic function with 1 method)
Let's evaluate the newly constructed gradient function at the solution [1,1].
gsol = rg([1,1])
2-element Array{Float64,1}:
1.4667356107373247e-8
-1.1102239280930583e-14
We are close to zero, but there are approximation errors, that can prevent the convergence to the right solution, or at least impact the solution accuracy, as
norm(gsol)
1.466735610737745e-8
storage = [0.0,0.0]
function rg!(storage::Vector, x::Vector)
s = rg(x)
storage[1:length(s)] = s[1:length(s)]
end
rg! (generic function with 1 method)
storage
2-element Array{Float64,1}:
0.0
0.0
@btime res = optimize(rosenbrock, rg!,
[0.0, 0.0],
Optim.BFGS(),
Optim.Options(g_tol = 1e-12,
store_trace = true,
show_trace = false))
62.899 μs (803 allocations: 44.81 KiB)
* Status: success
* Candidate solution
Minimizer: [1.00e+00, 1.00e+00]
Minimum: 5.378308e-17
* Found with
Algorithm: BFGS
Initial Point: [0.00e+00, 0.00e+00]
* Convergence measures
|x - x'| = 1.32e-10 ≰ 0.0e+00
|x - x'|/|x'| = 1.32e-10 ≰ 0.0e+00
|f(x) - f(x')| = 9.31e-19 ≰ 0.0e+00
|f(x) - f(x')|/|f(x')| = 1.73e-02 ≰ 0.0e+00
|g(x)| = 2.78e-13 ≤ 1.0e-12
* Work counters
Seconds run: 0 (vs limit Inf)
Iterations: 17
f(x) calls: 55
∇f(x) calls: 55
res = optimize(rosenbrock, rg!,
[1.1, 1.1],
Optim.GradientDescent(),
Optim.Options(g_tol = 1e-12,
store_trace = true,
show_trace = true))
Iter Function value Gradient norm
0 1.220000e+00 4.860000e+01
* time: 0.0009999275207519531
1 5.804214e-03 2.125407e+00
* time: 0.03600001335144043
2 3.342431e-03 4.583199e-02
* time: 0.0409998893737793
3 3.025234e-03 7.072574e-01
* time: 0.06200003623962402
4 2.774066e-03 1.561595e-01
* time: 0.10399985313415527
5 2.754813e-03 3.619916e-02
* time: 0.1099998950958252
6 2.735659e-03 1.553929e-01
* time: 0.1419999599456787
7 2.716594e-03 3.619630e-02
* time: 0.1549999713897705
8 2.695676e-03 1.642356e-01
* time: 0.18599987030029297
9 2.674873e-03 3.622467e-02
* time: 0.20799994468688965
10 2.651249e-03 1.769096e-01
* time: 0.21499991416931152
11 2.627785e-03 3.631260e-02
* time: 0.24199986457824707
12 2.599317e-03 1.979975e-01
* time: 0.2739999294281006
13 2.571002e-03 3.655250e-02
* time: 0.28299999237060547
14 2.530203e-03 2.437361e-01
* time: 0.2869999408721924
15 2.489586e-03 3.738017e-02
* time: 0.30299997329711914
16 2.334856e-03 5.027984e-01
* time: 0.33699989318847656
17 2.180480e-03 5.772634e-02
* time: 0.35699987411499023
18 2.177342e-03 4.660964e-02
* time: 0.37800002098083496
19 2.174207e-03 5.765494e-02
* time: 0.41100001335144043
20 2.171076e-03 4.653512e-02
* time: 0.4289999008178711
21 2.167949e-03 5.758317e-02
* time: 0.4500000476837158
22 2.164826e-03 4.646069e-02
* time: 0.4549999237060547
23 2.161707e-03 5.751145e-02
* time: 0.45799994468688965
24 2.158592e-03 4.638637e-02
* time: 0.4789998531341553
25 2.155481e-03 5.743979e-02
* time: 0.5190000534057617
26 2.152374e-03 4.631215e-02
* time: 0.5230000019073486
27 2.149271e-03 5.736818e-02
* time: 0.5350000858306885
28 2.146171e-03 4.623803e-02
* time: 0.5460000038146973
29 2.143076e-03 5.729662e-02
* time: 0.6039998531341553
30 2.139984e-03 4.616401e-02
* time: 0.6399998664855957
31 2.136897e-03 5.722512e-02
* time: 0.6440000534057617
32 2.133813e-03 4.609008e-02
* time: 0.6649999618530273
33 2.130733e-03 5.715367e-02
* time: 0.6700000762939453
34 2.127657e-03 4.601626e-02
* time: 0.6740000247955322
35 2.124585e-03 5.708228e-02
* time: 0.681999921798706
36 2.121517e-03 4.594253e-02
* time: 0.7170000076293945
37 2.118453e-03 5.701094e-02
* time: 0.7460000514984131
38 2.115393e-03 4.586891e-02
* time: 0.7850000858306885
39 2.112336e-03 5.693965e-02
* time: 0.8029999732971191
40 2.109283e-03 4.579538e-02
* time: 0.8190000057220459
41 2.106235e-03 5.686842e-02
* time: 0.8550000190734863
42 2.103190e-03 4.572195e-02
* time: 0.878000020980835
43 2.100149e-03 5.679724e-02
* time: 0.8899998664855957
44 2.097112e-03 4.564862e-02
* time: 0.8980000019073486
45 2.094078e-03 5.672612e-02
* time: 0.9140000343322754
46 2.091049e-03 4.557539e-02
* time: 0.9389998912811279
47 2.088023e-03 5.665505e-02
* time: 0.9689998626708984
48 2.085001e-03 4.550226e-02
* time: 1.0339999198913574
49 2.081984e-03 5.658403e-02
* time: 1.069000005722046
50 2.078969e-03 4.542923e-02
* time: 1.121000051498413
51 2.075959e-03 5.651306e-02
* time: 1.1399998664855957
52 2.072953e-03 4.535630e-02
* time: 1.2070000171661377
53 2.069950e-03 5.644215e-02
* time: 1.2379999160766602
54 2.066951e-03 4.528346e-02
* time: 1.251999855041504
55 2.063956e-03 5.637130e-02
* time: 1.2790000438690186
56 2.060965e-03 4.521072e-02
* time: 1.315999984741211
57 2.057978e-03 5.630050e-02
* time: 1.319000005722046
58 2.054994e-03 4.513809e-02
* time: 1.3399999141693115
59 2.052014e-03 5.622975e-02
* time: 1.3539998531341553
60 2.049038e-03 4.506555e-02
* time: 1.36899995803833
61 2.046066e-03 5.615905e-02
* time: 1.3999998569488525
62 2.043097e-03 4.499310e-02
* time: 1.430999994277954
63 2.040133e-03 5.608841e-02
* time: 1.4670000076293945
64 2.037172e-03 4.492076e-02
* time: 1.496999979019165
65 2.034215e-03 5.601782e-02
* time: 1.5709998607635498
66 2.031261e-03 4.484851e-02
* time: 1.6029999256134033
67 2.028312e-03 5.594729e-02
* time: 1.6989998817443848
68 2.025366e-03 4.477636e-02
* time: 1.7390000820159912
69 2.022424e-03 5.587681e-02
* time: 1.7979998588562012
70 2.019485e-03 4.470431e-02
* time: 1.8239998817443848
71 2.016551e-03 5.580638e-02
* time: 1.8380000591278076
72 2.013620e-03 4.463236e-02
* time: 1.8989999294281006
73 2.010693e-03 5.573601e-02
* time: 2.1010000705718994
74 2.007769e-03 4.456051e-02
* time: 2.1050000190734863
75 2.004850e-03 5.566569e-02
* time: 2.11899995803833
76 2.001934e-03 4.448875e-02
* time: 2.122999906539917
77 1.999022e-03 5.559543e-02
* time: 2.138000011444092
78 1.996113e-03 4.441709e-02
* time: 2.1589999198913574
79 1.993208e-03 5.552522e-02
* time: 2.1670000553131104
80 1.990307e-03 4.434553e-02
* time: 2.2039999961853027
81 1.987410e-03 5.545506e-02
* time: 2.2189998626708984
82 1.984516e-03 4.427406e-02
* time: 2.2269999980926514
83 1.981626e-03 5.538496e-02
* time: 2.247999906539917
84 1.978740e-03 4.420269e-02
* time: 2.2669999599456787
85 1.975858e-03 5.531491e-02
* time: 2.2720000743865967
86 1.972979e-03 4.413142e-02
* time: 2.2779998779296875
87 1.970104e-03 5.524491e-02
* time: 2.316999912261963
88 1.967232e-03 4.406025e-02
* time: 2.3489999771118164
89 1.964364e-03 5.517497e-02
* time: 2.3539998531341553
90 1.961500e-03 4.398917e-02
* time: 2.3569998741149902
91 1.958640e-03 5.510508e-02
* time: 2.374000072479248
92 1.955783e-03 4.391819e-02
* time: 2.3929998874664307
93 1.952930e-03 5.503525e-02
* time: 2.4110000133514404
94 1.950080e-03 4.384731e-02
* time: 2.437000036239624
95 1.947234e-03 5.496547e-02
* time: 2.4559998512268066
96 1.944392e-03 4.377653e-02
* time: 2.4719998836517334
97 1.941554e-03 5.489574e-02
* time: 2.4789998531341553
98 1.938718e-03 4.370584e-02
* time: 2.49399995803833
99 1.935887e-03 5.482606e-02
* time: 2.501999855041504
100 1.933060e-03 4.363524e-02
* time: 2.5220000743865967
101 1.930236e-03 5.475645e-02
* time: 2.558000087738037
102 1.927415e-03 4.356475e-02
* time: 2.5959999561309814
103 1.924598e-03 5.468688e-02
* time: 2.6080000400543213
104 1.921785e-03 4.349435e-02
* time: 2.624000072479248
105 1.918976e-03 5.461737e-02
* time: 2.6389999389648438
106 1.916170e-03 4.342404e-02
* time: 2.6559998989105225
107 1.913368e-03 5.454791e-02
* time: 2.672999858856201
108 1.910569e-03 4.335384e-02
* time: 2.690000057220459
109 1.907774e-03 5.447850e-02
* time: 2.7100000381469727
110 1.904982e-03 4.328373e-02
* time: 2.7170000076293945
111 1.902194e-03 5.440915e-02
* time: 2.7249999046325684
112 1.899410e-03 4.321371e-02
* time: 2.7279999256134033
113 1.896629e-03 5.433986e-02
* time: 2.746999979019165
114 1.893852e-03 4.314379e-02
* time: 2.7649998664855957
115 1.891078e-03 5.427061e-02
* time: 2.7990000247955322
116 1.888308e-03 4.307397e-02
* time: 2.828000068664551
117 1.885542e-03 5.420142e-02
* time: 2.8480000495910645
118 1.882779e-03 4.300424e-02
* time: 2.88700008392334
119 1.880020e-03 5.413229e-02
* time: 2.8910000324249268
120 1.877264e-03 4.293461e-02
* time: 2.8980000019073486
121 1.874512e-03 5.406321e-02
* time: 2.927999973297119
122 1.871763e-03 4.286507e-02
* time: 2.947999954223633
123 1.869018e-03 5.399418e-02
* time: 2.99399995803833
124 1.866276e-03 4.279563e-02
* time: 3.010999917984009
125 1.863538e-03 5.392520e-02
* time: 3.0199999809265137
126 1.860803e-03 4.272629e-02
* time: 3.0239999294281006
127 1.858073e-03 5.385628e-02
* time: 3.0320000648498535
128 1.855345e-03 4.265704e-02
* time: 3.059000015258789
129 1.852621e-03 5.378742e-02
* time: 3.072999954223633
130 1.849901e-03 4.258788e-02
* time: 3.1019999980926514
131 1.847184e-03 5.371860e-02
* time: 3.119999885559082
132 1.844470e-03 4.251883e-02
* time: 3.138000011444092
133 1.841761e-03 5.364985e-02
* time: 3.1710000038146973
134 1.839054e-03 4.244986e-02
* time: 3.187999963760376
135 1.836351e-03 5.358114e-02
* time: 3.2170000076293945
136 1.833652e-03 4.238099e-02
* time: 3.2309999465942383
137 1.830956e-03 5.351249e-02
* time: 3.253999948501587
138 1.828263e-03 4.231222e-02
* time: 3.259000062942505
139 1.825575e-03 5.344389e-02
* time: 3.2850000858306885
140 1.822889e-03 4.224354e-02
* time: 3.313999891281128
141 1.820207e-03 5.337535e-02
* time: 3.3389999866485596
142 1.817529e-03 4.217496e-02
* time: 3.3919999599456787
143 1.814854e-03 5.330686e-02
* time: 3.4179999828338623
144 1.812182e-03 4.210647e-02
* time: 3.4739999771118164
145 1.809514e-03 5.323842e-02
* time: 3.484999895095825
146 1.806849e-03 4.203807e-02
* time: 3.501999855041504
147 1.804188e-03 5.317004e-02
* time: 3.5279998779296875
148 1.801530e-03 4.196977e-02
* time: 3.5399999618530273
149 1.798876e-03 5.310171e-02
* time: 3.5429999828338623
150 1.796225e-03 4.190156e-02
* time: 3.5929999351501465
151 1.793578e-03 5.303343e-02
* time: 3.61899995803833
152 1.790934e-03 4.183345e-02
* time: 3.6449999809265137
153 1.788293e-03 5.296521e-02
* time: 3.6700000762939453
154 1.785656e-03 4.176543e-02
* time: 3.697000026702881
155 1.783023e-03 5.289705e-02
* time: 3.7260000705718994
156 1.780392e-03 4.169751e-02
* time: 3.739000082015991
157 1.777766e-03 5.282893e-02
* time: 3.7649998664855957
158 1.775142e-03 4.162968e-02
* time: 3.7809998989105225
159 1.772522e-03 5.276087e-02
* time: 3.816999912261963
160 1.769905e-03 4.156195e-02
* time: 3.825000047683716
161 1.767292e-03 5.269287e-02
* time: 3.8269999027252197
162 1.764682e-03 4.149431e-02
* time: 3.8439998626708984
163 1.762076e-03 5.262491e-02
* time: 3.8580000400543213
164 1.759473e-03 4.142676e-02
* time: 3.878000020980835
165 1.756874e-03 5.255702e-02
* time: 3.8949999809265137
166 1.754277e-03 4.135930e-02
* time: 3.9029998779296875
167 1.751684e-03 5.248917e-02
* time: 3.9070000648498535
168 1.749095e-03 4.129194e-02
* time: 3.921999931335449
169 1.746509e-03 5.242138e-02
* time: 3.950000047683716
170 1.743926e-03 4.122468e-02
* time: 3.9570000171661377
171 1.741347e-03 5.235364e-02
* time: 3.984999895095825
172 1.738771e-03 4.115750e-02
* time: 3.98799991607666
173 1.736198e-03 5.228596e-02
* time: 3.990999937057495
174 1.733629e-03 4.109042e-02
* time: 3.99399995803833
175 1.731063e-03 5.221833e-02
* time: 4.014999866485596
176 1.728500e-03 4.102344e-02
* time: 4.0329999923706055
177 1.725941e-03 5.215076e-02
* time: 4.050999879837036
178 1.723385e-03 4.095654e-02
* time: 4.069000005722046
179 1.720833e-03 5.208324e-02
* time: 4.088000059127808
180 1.718283e-03 4.088974e-02
* time: 4.116999864578247
181 1.715737e-03 5.201577e-02
* time: 4.144000053405762
182 1.713195e-03 4.082304e-02
* time: 4.158999919891357
183 1.710656e-03 5.194835e-02
* time: 4.167999982833862
184 1.708120e-03 4.075642e-02
* time: 4.185999870300293
185 1.705587e-03 5.188099e-02
* time: 4.194000005722046
186 1.703058e-03 4.068990e-02
* time: 4.216000080108643
187 1.700532e-03 5.181369e-02
* time: 4.23199987411499
188 1.698009e-03 4.062347e-02
* time: 4.244999885559082
189 1.695490e-03 5.174644e-02
* time: 4.260999917984009
190 1.692973e-03 4.055713e-02
* time: 4.283999919891357
191 1.690461e-03 5.167924e-02
* time: 4.308000087738037
192 1.687951e-03 4.049089e-02
* time: 4.322000026702881
193 1.685445e-03 5.161209e-02
* time: 4.325999975204468
194 1.682942e-03 4.042474e-02
* time: 4.328999996185303
195 1.680442e-03 5.154500e-02
* time: 4.349999904632568
196 1.677946e-03 4.035868e-02
* time: 4.368000030517578
197 1.675453e-03 5.147797e-02
* time: 4.381999969482422
198 1.672963e-03 4.029271e-02
* time: 4.38700008392334
199 1.670477e-03 5.141098e-02
* time: 4.389999866485596
200 1.667993e-03 4.022684e-02
* time: 4.4059998989105225
201 1.665513e-03 5.134406e-02
* time: 4.421999931335449
202 1.663036e-03 4.016106e-02
* time: 4.453000068664551
203 1.660563e-03 5.127718e-02
* time: 4.50600004196167
204 1.658092e-03 4.009537e-02
* time: 4.542999982833862
205 1.655625e-03 5.121036e-02
* time: 4.559000015258789
206 1.653162e-03 4.002977e-02
* time: 4.575000047683716
207 1.650701e-03 5.114359e-02
* time: 4.582000017166138
208 1.648244e-03 3.996426e-02
* time: 4.5950000286102295
209 1.645790e-03 5.107688e-02
* time: 4.61899995803833
210 1.643339e-03 3.989885e-02
* time: 4.644000053405762
211 1.640891e-03 5.101022e-02
* time: 4.683000087738037
212 1.638447e-03 3.983352e-02
* time: 4.70799994468689
213 1.636005e-03 5.094362e-02
* time: 4.710000038146973
214 1.633567e-03 3.976829e-02
* time: 4.7170000076293945
215 1.631133e-03 5.087706e-02
* time: 4.730999946594238
216 1.628701e-03 3.970315e-02
* time: 4.75600004196167
217 1.626273e-03 5.081057e-02
* time: 4.772000074386597
218 1.623847e-03 3.963810e-02
* time: 4.7850000858306885
219 1.621425e-03 5.074412e-02
* time: 4.802000045776367
220 1.619007e-03 3.957315e-02
* time: 4.816999912261963
221 1.616591e-03 5.067773e-02
* time: 4.822999954223633
222 1.614178e-03 3.950828e-02
* time: 4.82699990272522
223 1.611769e-03 5.061140e-02
* time: 4.841000080108643
224 1.609363e-03 3.944350e-02
* time: 4.85699987411499
225 1.606960e-03 5.054512e-02
* time: 4.859999895095825
226 1.604560e-03 3.937882e-02
* time: 4.88700008392334
227 1.602164e-03 5.047889e-02
* time: 4.901000022888184
228 1.599771e-03 3.931423e-02
* time: 4.914999961853027
229 1.597380e-03 5.041272e-02
* time: 4.924000024795532
230 1.594993e-03 3.924973e-02
* time: 4.960999965667725
231 1.592609e-03 5.034660e-02
* time: 4.978999853134155
232 1.590228e-03 3.918531e-02
* time: 5.009000062942505
233 1.587851e-03 5.028053e-02
* time: 5.01200008392334
234 1.585476e-03 3.912099e-02
* time: 5.0269999504089355
235 1.583105e-03 5.021452e-02
* time: 5.046999931335449
236 1.580737e-03 3.905676e-02
* time: 5.075000047683716
237 1.578372e-03 5.014856e-02
* time: 5.0899999141693115
238 1.576010e-03 3.899262e-02
* time: 5.119999885559082
239 1.573651e-03 5.008266e-02
* time: 5.124000072479248
240 1.571295e-03 3.892857e-02
* time: 5.138999938964844
241 1.568943e-03 5.001681e-02
* time: 5.1570000648498535
242 1.566593e-03 3.886461e-02
* time: 5.16700005531311
243 1.564247e-03 4.995101e-02
* time: 5.181999921798706
244 1.561903e-03 3.880075e-02
* time: 5.187000036239624
245 1.559563e-03 4.988527e-02
* time: 5.191999912261963
246 1.557226e-03 3.873697e-02
* time: 5.2170000076293945
247 1.554892e-03 4.981958e-02
* time: 5.241999864578247
248 1.552561e-03 3.867328e-02
* time: 5.253999948501587
249 1.550234e-03 4.975395e-02
* time: 5.2829999923706055
250 1.547909e-03 3.860968e-02
* time: 5.299999952316284
251 1.545588e-03 4.968837e-02
* time: 5.32099986076355
252 1.543269e-03 3.854617e-02
* time: 5.348999977111816
253 1.540954e-03 4.962285e-02
* time: 5.352999925613403
254 1.538641e-03 3.848275e-02
* time: 5.372999906539917
255 1.536332e-03 4.955737e-02
* time: 5.38700008392334
256 1.534026e-03 3.841942e-02
* time: 5.4049999713897705
257 1.531723e-03 4.949196e-02
* time: 5.431999921798706
258 1.529422e-03 3.835618e-02
* time: 5.45799994468689
259 1.527125e-03 4.942659e-02
* time: 5.476000070571899
260 1.524831e-03 3.829303e-02
* time: 5.489000082015991
261 1.522541e-03 4.936128e-02
* time: 5.496000051498413
262 1.520253e-03 3.822997e-02
* time: 5.5329999923706055
263 1.517968e-03 4.929603e-02
* time: 5.560999870300293
264 1.515686e-03 3.816700e-02
* time: 5.579999923706055
265 1.513407e-03 4.923083e-02
* time: 5.632999897003174
266 1.511131e-03 3.810412e-02
* time: 5.6549999713897705
267 1.508859e-03 4.916568e-02
* time: 5.690999984741211
268 1.506589e-03 3.804132e-02
* time: 5.704999923706055
269 1.504322e-03 4.910059e-02
* time: 5.70799994468689
270 1.502059e-03 3.797862e-02
* time: 5.723999977111816
271 1.499798e-03 4.903555e-02
* time: 5.73799991607666
272 1.497540e-03 3.791600e-02
* time: 5.75600004196167
273 1.495286e-03 4.897056e-02
* time: 5.759000062942505
274 1.493034e-03 3.785348e-02
* time: 5.773000001907349
275 1.490786e-03 4.890563e-02
* time: 5.812000036239624
276 1.488540e-03 3.779104e-02
* time: 5.83299994468689
277 1.486298e-03 4.884076e-02
* time: 5.861000061035156
278 1.484058e-03 3.772869e-02
* time: 5.879999876022339
279 1.481821e-03 4.877593e-02
* time: 5.895999908447266
280 1.479588e-03 3.766643e-02
* time: 5.928999900817871
281 1.477357e-03 4.871117e-02
* time: 5.953000068664551
282 1.475129e-03 3.760426e-02
* time: 5.971999883651733
283 1.472905e-03 4.864645e-02
* time: 6.006999969482422
284 1.470683e-03 3.754217e-02
* time: 6.009999990463257
285 1.468464e-03 4.858179e-02
* time: 6.026000022888184
286 1.466249e-03 3.748018e-02
* time: 6.0290000438690186
287 1.464036e-03 4.851719e-02
* time: 6.042999982833862
288 1.461826e-03 3.741827e-02
* time: 6.058000087738037
289 1.459619e-03 4.845263e-02
* time: 6.072000026702881
290 1.457415e-03 3.735645e-02
* time: 6.085000038146973
291 1.455214e-03 4.838814e-02
* time: 6.109999895095825
292 1.453016e-03 3.729472e-02
* time: 6.145999908447266
293 1.450821e-03 4.832369e-02
* time: 6.151000022888184
294 1.448629e-03 3.723308e-02
* time: 6.171000003814697
295 1.446440e-03 4.825930e-02
* time: 6.174999952316284
296 1.444253e-03 3.717152e-02
* time: 6.190000057220459
297 1.442070e-03 4.819497e-02
* time: 6.240000009536743
298 1.439890e-03 3.711005e-02
* time: 6.254999876022339
299 1.437712e-03 4.813069e-02
* time: 6.2779998779296875
300 1.435537e-03 3.704867e-02
* time: 6.318000078201294
301 1.433366e-03 4.806646e-02
* time: 6.323999881744385
302 1.431197e-03 3.698738e-02
* time: 6.348999977111816
303 1.429031e-03 4.800229e-02
* time: 6.376999855041504
304 1.426868e-03 3.692618e-02
* time: 6.398999929428101
305 1.424708e-03 4.793817e-02
* time: 6.4029998779296875
306 1.422551e-03 3.686506e-02
* time: 6.417999982833862
307 1.420397e-03 4.787411e-02
* time: 6.427000045776367
308 1.418246e-03 3.680403e-02
* time: 6.440999984741211
309 1.416097e-03 4.781010e-02
* time: 6.4700000286102295
310 1.413952e-03 3.674309e-02
* time: 6.506999969482422
311 1.411809e-03 4.774614e-02
* time: 6.5249998569488525
312 1.409669e-03 3.668223e-02
* time: 6.536999940872192
313 1.407532e-03 4.768224e-02
* time: 6.582000017166138
314 1.405398e-03 3.662146e-02
* time: 6.596999883651733
315 1.403267e-03 4.761839e-02
* time: 6.603999853134155
316 1.401139e-03 3.656078e-02
* time: 6.61899995803833
317 1.399013e-03 4.755460e-02
* time: 6.647000074386597
318 1.396891e-03 3.650018e-02
* time: 6.6540000438690186
319 1.394771e-03 4.749086e-02
* time: 6.670000076293945
320 1.392654e-03 3.643968e-02
* time: 6.684000015258789
321 1.390540e-03 4.742717e-02
* time: 6.7230000495910645
322 1.388429e-03 3.637925e-02
* time: 6.726000070571899
323 1.386321e-03 4.736354e-02
* time: 6.773000001907349
324 1.384215e-03 3.631892e-02
* time: 6.800999879837036
325 1.382113e-03 4.729997e-02
* time: 6.852999925613403
326 1.380013e-03 3.625867e-02
* time: 6.924000024795532
327 1.377916e-03 4.723645e-02
* time: 6.948999881744385
328 1.375822e-03 3.619851e-02
* time: 6.976999998092651
329 1.373731e-03 4.717298e-02
* time: 7.00600004196167
330 1.371642e-03 3.613843e-02
* time: 7.01200008392334
331 1.369557e-03 4.710957e-02
* time: 7.046999931335449
332 1.367474e-03 3.607844e-02
* time: 7.052000045776367
333 1.365394e-03 4.704621e-02
* time: 7.072000026702881
334 1.363316e-03 3.601854e-02
* time: 7.0980000495910645
335 1.361242e-03 4.698290e-02
* time: 7.102999925613403
336 1.359170e-03 3.595872e-02
* time: 7.116999864578247
337 1.357102e-03 4.691965e-02
* time: 7.164999961853027
338 1.355036e-03 3.589899e-02
* time: 7.187999963760376
339 1.352973e-03 4.685646e-02
* time: 7.190000057220459
340 1.350912e-03 3.583934e-02
* time: 7.193000078201294
341 1.348855e-03 4.679331e-02
* time: 7.2179999351501465
342 1.346800e-03 3.577978e-02
* time: 7.221999883651733
343 1.344748e-03 4.673023e-02
* time: 7.23799991607666
344 1.342698e-03 3.572031e-02
* time: 7.263999938964844
345 1.340652e-03 4.666719e-02
* time: 7.2809998989105225
346 1.338608e-03 3.566092e-02
* time: 7.308000087738037
347 1.336567e-03 4.660421e-02
* time: 7.335000038146973
348 1.334529e-03 3.560162e-02
* time: 7.341000080108643
349 1.332494e-03 4.654129e-02
* time: 7.343999862670898
350 1.330461e-03 3.554240e-02
* time: 7.359999895095825
351 1.328431e-03 4.647842e-02
* time: 7.366999864578247
352 1.326404e-03 3.548327e-02
* time: 7.384000062942505
353 1.324380e-03 4.641560e-02
* time: 7.401000022888184
354 1.322358e-03 3.542422e-02
* time: 7.4079999923706055
355 1.320339e-03 4.635284e-02
* time: 7.421000003814697
356 1.318323e-03 3.536526e-02
* time: 7.424999952316284
357 1.316309e-03 4.629014e-02
* time: 7.427999973297119
358 1.314299e-03 3.530638e-02
* time: 7.46399998664856
359 1.312291e-03 4.622748e-02
* time: 7.483999967575073
360 1.310286e-03 3.524759e-02
* time: 7.496999979019165
361 1.308283e-03 4.616488e-02
* time: 7.510999917984009
362 1.306283e-03 3.518888e-02
* time: 7.523999929428101
363 1.304286e-03 4.610234e-02
* time: 7.537999868392944
364 1.302292e-03 3.513025e-02
* time: 7.559000015258789
365 1.300300e-03 4.603985e-02
* time: 7.572000026702881
366 1.298311e-03 3.507172e-02
* time: 7.575000047683716
367 1.296325e-03 4.597742e-02
* time: 7.58899998664856
368 1.294342e-03 3.501326e-02
* time: 7.605999946594238
369 1.292361e-03 4.591504e-02
* time: 7.621000051498413
370 1.290383e-03 3.495489e-02
* time: 7.63700008392334
371 1.288407e-03 4.585271e-02
* time: 7.651000022888184
372 1.286435e-03 3.489661e-02
* time: 7.670000076293945
373 1.284465e-03 4.579044e-02
* time: 7.684999942779541
374 1.282497e-03 3.483841e-02
* time: 7.703000068664551
375 1.280533e-03 4.572822e-02
* time: 7.73199987411499
376 1.278571e-03 3.478029e-02
* time: 7.739000082015991
377 1.276611e-03 4.566606e-02
* time: 7.756999969482422
378 1.274655e-03 3.472226e-02
* time: 7.769999980926514
379 1.272701e-03 4.560395e-02
* time: 7.7769999504089355
380 1.270750e-03 3.466431e-02
* time: 7.792999982833862
381 1.268801e-03 4.554189e-02
* time: 7.810999870300293
382 1.266855e-03 3.460644e-02
* time: 7.838000059127808
383 1.264912e-03 4.547989e-02
* time: 7.841000080108643
384 1.262971e-03 3.454866e-02
* time: 7.866999864578247
385 1.261033e-03 4.541795e-02
* time: 7.871000051498413
386 1.259098e-03 3.449097e-02
* time: 7.884999990463257
387 1.257165e-03 4.535606e-02
* time: 7.915999889373779
388 1.255235e-03 3.443335e-02
* time: 7.930000066757202
389 1.253308e-03 4.529422e-02
* time: 7.955999851226807
390 1.251383e-03 3.437582e-02
* time: 7.96399998664856
391 1.249461e-03 4.523244e-02
* time: 7.9709999561309814
392 1.247541e-03 3.431838e-02
* time: 7.977999925613403
393 1.245624e-03 4.517071e-02
* time: 7.99399995803833
394 1.243710e-03 3.426101e-02
* time: 8.001999855041504
395 1.241798e-03 4.510904e-02
* time: 8.023000001907349
396 1.239889e-03 3.420373e-02
* time: 8.027999877929688
397 1.237983e-03 4.504742e-02
* time: 8.035000085830688
398 1.236079e-03 3.414654e-02
* time: 8.055000066757202
399 1.234178e-03 4.498586e-02
* time: 8.073999881744385
400 1.232279e-03 3.408942e-02
* time: 8.105000019073486
401 1.230383e-03 4.492435e-02
* time: 8.126999855041504
402 1.228490e-03 3.403239e-02
* time: 8.157000064849854
403 1.226599e-03 4.486289e-02
* time: 8.198999881744385
404 1.224711e-03 3.397544e-02
* time: 8.223000049591064
405 1.222826e-03 4.480149e-02
* time: 8.260999917984009
406 1.220943e-03 3.391858e-02
* time: 8.287999868392944
407 1.219062e-03 4.474015e-02
* time: 8.305000066757202
408 1.217184e-03 3.386180e-02
* time: 8.322999954223633
409 1.215309e-03 4.467886e-02
* time: 8.336999893188477
410 1.213436e-03 3.380510e-02
* time: 8.341000080108643
411 1.211566e-03 4.461762e-02
* time: 8.343999862670898
412 1.209699e-03 3.374848e-02
* time: 8.361000061035156
413 1.207834e-03 4.455644e-02
* time: 8.378000020980835
414 1.205971e-03 3.369195e-02
* time: 8.40499997138977
415 1.204112e-03 4.449531e-02
* time: 8.434999942779541
416 1.202254e-03 3.363549e-02
* time: 8.45300006866455
417 1.200400e-03 4.443424e-02
* time: 8.471999883651733
418 1.198548e-03 3.357912e-02
* time: 8.496999979019165
419 1.196698e-03 4.437322e-02
* time: 8.503999948501587
420 1.194851e-03 3.352284e-02
* time: 8.519000053405762
421 1.193006e-03 4.431225e-02
* time: 8.533999919891357
422 1.191164e-03 3.346663e-02
* time: 8.572999954223633
423 1.189325e-03 4.425134e-02
* time: 8.596999883651733
424 1.187488e-03 3.341051e-02
* time: 8.625999927520752
425 1.185654e-03 4.419049e-02
* time: 8.675999879837036
426 1.183822e-03 3.335447e-02
* time: 8.680999994277954
427 1.181993e-03 4.412969e-02
* time: 8.714999914169312
428 1.180166e-03 3.329851e-02
* time: 8.753999948501587
429 1.178342e-03 4.406894e-02
* time: 8.772000074386597
430 1.176520e-03 3.324263e-02
* time: 8.789999961853027
431 1.174701e-03 4.400825e-02
* time: 8.806999921798706
432 1.172884e-03 3.318683e-02
* time: 8.83899998664856
433 1.171070e-03 4.394761e-02
* time: 8.855999946594238
434 1.169258e-03 3.313112e-02
* time: 8.874000072479248
435 1.167449e-03 4.388703e-02
* time: 8.888999938964844
436 1.165642e-03 3.307548e-02
* time: 8.927000045776367
437 1.163838e-03 4.382650e-02
* time: 8.930999994277954
438 1.162036e-03 3.301993e-02
* time: 8.94700002670288
439 1.160237e-03 4.376603e-02
* time: 8.95300006866455
440 1.158440e-03 3.296446e-02
* time: 8.95799994468689
441 1.156646e-03 4.370561e-02
* time: 8.9760000705719
442 1.154854e-03 3.290907e-02
* time: 8.990000009536743
443 1.153065e-03 4.364525e-02
* time: 8.994999885559082
444 1.151278e-03 3.285376e-02
* time: 9.003000020980835
445 1.149494e-03 4.358494e-02
* time: 9.032000064849854
446 1.147712e-03 3.279853e-02
* time: 9.04099988937378
447 1.145933e-03 4.352469e-02
* time: 9.055999994277954
448 1.144156e-03 3.274339e-02
* time: 9.075999975204468
449 1.142381e-03 4.346449e-02
* time: 9.08299994468689
450 1.140609e-03 3.268832e-02
* time: 9.10699987411499
451 1.138840e-03 4.340434e-02
* time: 9.144999980926514
452 1.137073e-03 3.263333e-02
* time: 9.160000085830688
453 1.135308e-03 4.334425e-02
* time: 9.184999942779541
454 1.133546e-03 3.257843e-02
* time: 9.226999998092651
455 1.131786e-03 4.328422e-02
* time: 9.249000072479248
456 1.130029e-03 3.252361e-02
* time: 9.264999866485596
457 1.128274e-03 4.322423e-02
* time: 9.274999856948853
458 1.126522e-03 3.246886e-02
* time: 9.280999898910522
459 1.124772e-03 4.316431e-02
* time: 9.322999954223633
460 1.123024e-03 3.241420e-02
* time: 9.345999956130981
461 1.121279e-03 4.310444e-02
* time: 9.384999990463257
462 1.119536e-03 3.235962e-02
* time: 9.394000053405762
463 1.117796e-03 4.304462e-02
* time: 9.3989999294281
464 1.116058e-03 3.230511e-02
* time: 9.444999933242798
465 1.114323e-03 4.298486e-02
* time: 9.49399995803833
466 1.112590e-03 3.225069e-02
* time: 9.532000064849854
467 1.110859e-03 4.292515e-02
* time: 9.555999994277954
468 1.109131e-03 3.219635e-02
* time: 9.57699990272522
469 1.107405e-03 4.286550e-02
* time: 9.621999979019165
470 1.105682e-03 3.214209e-02
* time: 9.65499997138977
471 1.103961e-03 4.280590e-02
* time: 9.684999942779541
472 1.102242e-03 3.208790e-02
* time: 9.700000047683716
473 1.100526e-03 4.274635e-02
* time: 9.769000053405762
474 1.098812e-03 3.203380e-02
* time: 9.78600001335144
475 1.097101e-03 4.268686e-02
* time: 9.822999954223633
476 1.095392e-03 3.197978e-02
* time: 9.839999914169312
477 1.093685e-03 4.262743e-02
* time: 9.853999853134155
478 1.091981e-03 3.192583e-02
* time: 9.891999959945679
479 1.090279e-03 4.256805e-02
* time: 9.898000001907349
480 1.088580e-03 3.187197e-02
* time: 9.920000076293945
481 1.086883e-03 4.250873e-02
* time: 9.960000038146973
482 1.085188e-03 3.181818e-02
* time: 9.973999977111816
483 1.083495e-03 4.244946e-02
* time: 9.993000030517578
484 1.081805e-03 3.176448e-02
* time: 10.02999997138977
485 1.080118e-03 4.239024e-02
* time: 10.045000076293945
486 1.078432e-03 3.171085e-02
* time: 10.066999912261963
487 1.076749e-03 4.233108e-02
* time: 10.075999975204468
488 1.075069e-03 3.165730e-02
* time: 10.098000049591064
489 1.073391e-03 4.227197e-02
* time: 10.102999925613403
490 1.071715e-03 3.160383e-02
* time: 10.14299988746643
491 1.070041e-03 4.221292e-02
* time: 10.157000064849854
492 1.068370e-03 3.155044e-02
* time: 10.174999952316284
493 1.066701e-03 4.215393e-02
* time: 10.180000066757202
494 1.065034e-03 3.149713e-02
* time: 10.188999891281128
495 1.063370e-03 4.209498e-02
* time: 10.210999965667725
496 1.061708e-03 3.144390e-02
* time: 10.253999948501587
497 1.060049e-03 4.203610e-02
* time: 10.282999992370605
498 1.058391e-03 3.139075e-02
* time: 10.289999961853027
499 1.056737e-03 4.197726e-02
* time: 10.318000078201294
500 1.055084e-03 3.133767e-02
* time: 10.33299994468689
501 1.053434e-03 4.191849e-02
* time: 10.381999969482422
502 1.051786e-03 3.128467e-02
* time: 10.421000003814697
503 1.050140e-03 4.185976e-02
* time: 10.45300006866455
504 1.048497e-03 3.123176e-02
* time: 10.473000049591064
505 1.046856e-03 4.180110e-02
* time: 10.489000082015991
506 1.045217e-03 3.117892e-02
* time: 10.524999856948853
507 1.043581e-03 4.174248e-02
* time: 10.549000024795532
508 1.041946e-03 3.112616e-02
* time: 10.569999933242798
509 1.040315e-03 4.168392e-02
* time: 10.585999965667725
510 1.038685e-03 3.107347e-02
* time: 10.615000009536743
511 1.037058e-03 4.162542e-02
* time: 10.661999940872192
512 1.035433e-03 3.102087e-02
* time: 10.710000038146973
513 1.033810e-03 4.156697e-02
* time: 10.73799991607666
514 1.032190e-03 3.096834e-02
* time: 10.805999994277954
515 1.030572e-03 4.150858e-02
* time: 10.842000007629395
516 1.028956e-03 3.091589e-02
* time: 10.846999883651733
517 1.027342e-03 4.145024e-02
* time: 10.884999990463257
518 1.025731e-03 3.086352e-02
* time: 10.894000053405762
519 1.024122e-03 4.139195e-02
* time: 10.91100001335144
520 1.022515e-03 3.081122e-02
* time: 10.925999879837036
521 1.020911e-03 4.133372e-02
* time: 10.948999881744385
522 1.019308e-03 3.075901e-02
* time: 10.966000080108643
523 1.017708e-03 4.127555e-02
* time: 11.004999876022339
524 1.016111e-03 3.070687e-02
* time: 11.024999856948853
525 1.014515e-03 4.121743e-02
* time: 11.066999912261963
526 1.012922e-03 3.065481e-02
* time: 11.082000017166138
527 1.011331e-03 4.115936e-02
* time: 11.089999914169312
528 1.009742e-03 3.060282e-02
* time: 11.122999906539917
529 1.008156e-03 4.110135e-02
* time: 11.141000032424927
530 1.006571e-03 3.055091e-02
* time: 11.170000076293945
531 1.004990e-03 4.104340e-02
* time: 11.198999881744385
532 1.003410e-03 3.049908e-02
* time: 11.208999872207642
533 1.001832e-03 4.098550e-02
* time: 11.233999967575073
534 1.000257e-03 3.044733e-02
* time: 11.263999938964844
535 9.986837e-04 4.092765e-02
* time: 11.277999877929688
536 9.971128e-04 3.039565e-02
* time: 11.29699993133545
537 9.955441e-04 4.086986e-02
* time: 11.310999870300293
538 9.939776e-04 3.034406e-02
* time: 11.330999851226807
539 9.924135e-04 4.081212e-02
* time: 11.338000059127808
540 9.908514e-04 3.029253e-02
* time: 11.355000019073486
541 9.892916e-04 4.075444e-02
* time: 11.358999967575073
542 9.877339e-04 3.024109e-02
* time: 11.361999988555908
543 9.861786e-04 4.069681e-02
* time: 11.376999855041504
544 9.846253e-04 3.018972e-02
* time: 11.39299988746643
545 9.830744e-04 4.063924e-02
* time: 11.408999919891357
546 9.815255e-04 3.013843e-02
* time: 11.424999952316284
547 9.799789e-04 4.058172e-02
* time: 11.454999923706055
548 9.784345e-04 3.008721e-02
* time: 11.471999883651733
549 9.768923e-04 4.052426e-02
* time: 11.499000072479248
550 9.753522e-04 3.003607e-02
* time: 11.516999959945679
551 9.738143e-04 4.046685e-02
* time: 11.560999870300293
552 9.722786e-04 2.998501e-02
* time: 11.569000005722046
553 9.707451e-04 4.040950e-02
* time: 11.586999893188477
554 9.692137e-04 2.993402e-02
* time: 11.592999935150146
555 9.676846e-04 4.035220e-02
* time: 11.608999967575073
556 9.661576e-04 2.988311e-02
* time: 11.626999855041504
557 9.646328e-04 4.029496e-02
* time: 11.644999980926514
558 9.631101e-04 2.983227e-02
* time: 11.662999868392944
559 9.615896e-04 4.023777e-02
* time: 11.66700005531311
560 9.600712e-04 2.978151e-02
* time: 11.694999933242798
561 9.585551e-04 4.018064e-02
* time: 11.708999872207642
562 9.570410e-04 2.973083e-02
* time: 11.727999925613403
563 9.555292e-04 4.012356e-02
* time: 11.733000040054321
564 9.540194e-04 2.968022e-02
* time: 11.736000061035156
565 9.525118e-04 4.006654e-02
* time: 11.74399995803833
566 9.510063e-04 2.962969e-02
* time: 11.766000032424927
567 9.495031e-04 4.000957e-02
* time: 11.785000085830688
568 9.480019e-04 2.957923e-02
* time: 11.803999900817871
569 9.465029e-04 3.995265e-02
* time: 11.832000017166138
570 9.450059e-04 2.952885e-02
* time: 11.869999885559082
571 9.435112e-04 3.989580e-02
* time: 11.8989999294281
572 9.420185e-04 2.947854e-02
* time: 11.938999891281128
573 9.405281e-04 3.983899e-02
* time: 11.94700002670288
574 9.390396e-04 2.942831e-02
* time: 11.961999893188477
575 9.375534e-04 3.978224e-02
* time: 11.98199987411499
576 9.360692e-04 2.937816e-02
* time: 12.010999917984009
577 9.345872e-04 3.972555e-02
* time: 12.022000074386597
578 9.331072e-04 2.932808e-02
* time: 12.030999898910522
579 9.316295e-04 3.966891e-02
* time: 12.049000024795532
580 9.301537e-04 2.927807e-02
* time: 12.069000005722046
581 9.286802e-04 3.961232e-02
* time: 12.083999872207642
582 9.272086e-04 2.922814e-02
* time: 12.089999914169312
583 9.257393e-04 3.955579e-02
* time: 12.109999895095825
584 9.242719e-04 2.917828e-02
* time: 12.138000011444092
585 9.228067e-04 3.949932e-02
* time: 12.155999898910522
586 9.213436e-04 2.912850e-02
* time: 12.160000085830688
587 9.198826e-04 3.944290e-02
* time: 12.174000024795532
588 9.184236e-04 2.907880e-02
* time: 12.198999881744385
589 9.169668e-04 3.938653e-02
* time: 12.216000080108643
590 9.155120e-04 2.902916e-02
* time: 12.244999885559082
591 9.140593e-04 3.933022e-02
* time: 12.273000001907349
592 9.126087e-04 2.897961e-02
* time: 12.305999994277954
593 9.111602e-04 3.927397e-02
* time: 12.325000047683716
594 9.097137e-04 2.893012e-02
* time: 12.342000007629395
595 9.082693e-04 3.921777e-02
* time: 12.358999967575073
596 9.068269e-04 2.888072e-02
* time: 12.365999937057495
597 9.053867e-04 3.916162e-02
* time: 12.394000053405762
598 9.039484e-04 2.883138e-02
* time: 12.399999856948853
599 9.025124e-04 3.910553e-02
* time: 12.41599988937378
600 9.010782e-04 2.878212e-02
* time: 12.440999984741211
601 8.996462e-04 3.904949e-02
* time: 12.476999998092651
602 8.982162e-04 2.873293e-02
* time: 12.494999885559082
603 8.967883e-04 3.899351e-02
* time: 12.5
604 8.953624e-04 2.868382e-02
* time: 12.516000032424927
605 8.939386e-04 3.893759e-02
* time: 12.520999908447266
606 8.925167e-04 2.863478e-02
* time: 12.527999877929688
607 8.910970e-04 3.888171e-02
* time: 12.535000085830688
608 8.896792e-04 2.858582e-02
* time: 12.549000024795532
609 8.882636e-04 3.882590e-02
* time: 12.55299997329712
610 8.868499e-04 2.853693e-02
* time: 12.578999996185303
611 8.854383e-04 3.877014e-02
* time: 12.598000049591064
612 8.840286e-04 2.848811e-02
* time: 12.631999969482422
613 8.826211e-04 3.871443e-02
* time: 12.648000001907349
614 8.812155e-04 2.843937e-02
* time: 12.654000043869019
615 8.798120e-04 3.865878e-02
* time: 12.67199993133545
616 8.784105e-04 2.839070e-02
* time: 12.687999963760376
617 8.770110e-04 3.860318e-02
* time: 12.70799994468689
618 8.756135e-04 2.834210e-02
* time: 12.734999895095825
619 8.742180e-04 3.854764e-02
* time: 12.753000020980835
620 8.728245e-04 2.829358e-02
* time: 12.769000053405762
621 8.714331e-04 3.849215e-02
* time: 12.819000005722046
622 8.700435e-04 2.824513e-02
* time: 12.841000080108643
623 8.686561e-04 3.843672e-02
* time: 12.861999988555908
624 8.672706e-04 2.819675e-02
* time: 12.894999980926514
625 8.658872e-04 3.838134e-02
* time: 12.91100001335144
626 8.645056e-04 2.814844e-02
* time: 12.918999910354614
627 8.631262e-04 3.832602e-02
* time: 12.933000087738037
628 8.617486e-04 2.810021e-02
* time: 12.950000047683716
629 8.603732e-04 3.827075e-02
* time: 12.964999914169312
630 8.589996e-04 2.805205e-02
* time: 12.980000019073486
631 8.576281e-04 3.821554e-02
* time: 12.983999967575073
632 8.562584e-04 2.800397e-02
* time: 12.994999885559082
633 8.548909e-04 3.816038e-02
* time: 13.039999961853027
634 8.535252e-04 2.795595e-02
* time: 13.053999900817871
635 8.521616e-04 3.810528e-02
* time: 13.07099986076355
636 8.507998e-04 2.790801e-02
* time: 13.086999893188477
637 8.494402e-04 3.805023e-02
* time: 13.115999937057495
638 8.480823e-04 2.786015e-02
* time: 13.132999897003174
639 8.467266e-04 3.799523e-02
* time: 13.162999868392944
640 8.453727e-04 2.781235e-02
* time: 13.180000066757202
641 8.440208e-04 3.794030e-02
* time: 13.198999881744385
642 8.426708e-04 2.776463e-02
* time: 13.20300006866455
643 8.413229e-04 3.788541e-02
* time: 13.233999967575073
644 8.399768e-04 2.771697e-02
* time: 13.247999906539917
645 8.386328e-04 3.783058e-02
* time: 13.263000011444092
646 8.372906e-04 2.766940e-02
* time: 13.276999950408936
647 8.359504e-04 3.777581e-02
* time: 13.293999910354614
648 8.346121e-04 2.762189e-02
* time: 13.309999942779541
649 8.332758e-04 3.772109e-02
* time: 13.352999925613403
650 8.319414e-04 2.757445e-02
* time: 13.371999979019165
651 8.306090e-04 3.766643e-02
* time: 13.376999855041504
652 8.292784e-04 2.752709e-02
* time: 13.407999992370605
653 8.279498e-04 3.761182e-02
* time: 13.414000034332275
654 8.266231e-04 2.747980e-02
* time: 13.41599988937378
655 8.252984e-04 3.755726e-02
* time: 13.417999982833862
656 8.239755e-04 2.743258e-02
* time: 13.42799997329712
657 8.226546e-04 3.750276e-02
* time: 13.44700002670288
658 8.213356e-04 2.738543e-02
* time: 13.463000059127808
659 8.200185e-04 3.744832e-02
* time: 13.491999864578247
660 8.187033e-04 2.733835e-02
* time: 13.496999979019165
661 8.173900e-04 3.739393e-02
* time: 13.513000011444092
662 8.160786e-04 2.729135e-02
* time: 13.5239999294281
663 8.147692e-04 3.733959e-02
* time: 13.54099988937378
664 8.134616e-04 2.724441e-02
* time: 13.601999998092651
665 8.121560e-04 3.728531e-02
* time: 13.622999906539917
666 8.108522e-04 2.719755e-02
* time: 13.657999992370605
667 8.095503e-04 3.723109e-02
* time: 13.664000034332275
668 8.082503e-04 2.715076e-02
* time: 13.678999900817871
669 8.069522e-04 3.717692e-02
* time: 13.684999942779541
670 8.056560e-04 2.710404e-02
* time: 13.710000038146973
671 8.043617e-04 3.712280e-02
* time: 13.71399998664856
672 8.030692e-04 2.705739e-02
* time: 13.717000007629395
673 8.017787e-04 3.706874e-02
* time: 13.73199987411499
674 8.004900e-04 2.701081e-02
* time: 13.751999855041504
675 7.992032e-04 3.701474e-02
* time: 13.766999959945679
676 7.979182e-04 2.696431e-02
* time: 13.785000085830688
677 7.966352e-04 3.696078e-02
* time: 13.799000024795532
678 7.953539e-04 2.691787e-02
* time: 13.812999963760376
679 7.940747e-04 3.690689e-02
* time: 13.82699990272522
680 7.927971e-04 2.687150e-02
* time: 13.848000049591064
681 7.915216e-04 3.685305e-02
* time: 13.8510000705719
682 7.902478e-04 2.682521e-02
* time: 13.881999969482422
683 7.889759e-04 3.679926e-02
* time: 13.898000001907349
684 7.877058e-04 2.677898e-02
* time: 13.912999868392944
685 7.864377e-04 3.674553e-02
* time: 13.950000047683716
686 7.851713e-04 2.673283e-02
* time: 13.95799994468689
687 7.839069e-04 3.669185e-02
* time: 13.991999864578247
688 7.826442e-04 2.668674e-02
* time: 14.014999866485596
689 7.813834e-04 3.663823e-02
* time: 14.033999919891357
690 7.801244e-04 2.664073e-02
* time: 14.05299997329712
691 7.788673e-04 3.658466e-02
* time: 14.078999996185303
692 7.776120e-04 2.659479e-02
* time: 14.1010000705719
693 7.763586e-04 3.653115e-02
* time: 14.115999937057495
694 7.751069e-04 2.654891e-02
* time: 14.141000032424927
695 7.738572e-04 3.647769e-02
* time: 14.158999919891357
696 7.726092e-04 2.650311e-02
* time: 14.208999872207642
697 7.713631e-04 3.642429e-02
* time: 14.218999862670898
698 7.701187e-04 2.645738e-02
* time: 14.29699993133545
699 7.688762e-04 3.637094e-02
* time: 14.313999891281128
700 7.676355e-04 2.641171e-02
* time: 14.351999998092651
701 7.663967e-04 3.631765e-02
* time: 14.36899995803833
702 7.651596e-04 2.636612e-02
* time: 14.398000001907349
703 7.639244e-04 3.626441e-02
* time: 14.414000034332275
704 7.626909e-04 2.632059e-02
* time: 14.418999910354614
705 7.614593e-04 3.621123e-02
* time: 14.450000047683716
706 7.602294e-04 2.627514e-02
* time: 14.500999927520752
707 7.590014e-04 3.615810e-02
* time: 14.51799988746643
708 7.577752e-04 2.622975e-02
* time: 14.552000045776367
709 7.565508e-04 3.610502e-02
* time: 14.589999914169312
710 7.553281e-04 2.618444e-02
* time: 14.605999946594238
711 7.541073e-04 3.605200e-02
* time: 14.625
712 7.528882e-04 2.613919e-02
* time: 14.641999959945679
713 7.516710e-04 3.599904e-02
* time: 14.667999982833862
714 7.504555e-04 2.609401e-02
* time: 14.684000015258789
715 7.492418e-04 3.594613e-02
* time: 14.693000078201294
716 7.480298e-04 2.604890e-02
* time: 14.726999998092651
717 7.468197e-04 3.589328e-02
* time: 14.744999885559082
718 7.456113e-04 2.600387e-02
* time: 14.764999866485596
719 7.444048e-04 3.584048e-02
* time: 14.782000064849854
720 7.431999e-04 2.595890e-02
* time: 14.786999940872192
721 7.419969e-04 3.578773e-02
* time: 14.810999870300293
722 7.407956e-04 2.591399e-02
* time: 14.82699990272522
723 7.395962e-04 3.573504e-02
* time: 14.842000007629395
724 7.383984e-04 2.586916e-02
* time: 14.846999883651733
725 7.372024e-04 3.568240e-02
* time: 14.875
726 7.360081e-04 2.582440e-02
* time: 14.894000053405762
727 7.348157e-04 3.562982e-02
* time: 14.912999868392944
728 7.336250e-04 2.577970e-02
* time: 14.917999982833862
729 7.324360e-04 3.557730e-02
* time: 14.937000036239624
730 7.312488e-04 2.573508e-02
* time: 14.960000038146973
731 7.300634e-04 3.552483e-02
* time: 14.983000040054321
732 7.288796e-04 2.569052e-02
* time: 15.023000001907349
733 7.276977e-04 3.547241e-02
* time: 15.059999942779541
734 7.265174e-04 2.564603e-02
* time: 15.079999923706055
735 7.253389e-04 3.542005e-02
* time: 15.103999853134155
736 7.241621e-04 2.560161e-02
* time: 15.315000057220459
737 7.229871e-04 3.536774e-02
* time: 15.342000007629395
738 7.218138e-04 2.555725e-02
* time: 15.353999853134155
739 7.206423e-04 3.531549e-02
* time: 15.361000061035156
740 7.194724e-04 2.551297e-02
* time: 15.365000009536743
741 7.183043e-04 3.526329e-02
* time: 15.378000020980835
742 7.171379e-04 2.546875e-02
* time: 15.402999877929688
743 7.159733e-04 3.521115e-02
* time: 15.440000057220459
744 7.148103e-04 2.542460e-02
* time: 15.473999977111816
745 7.136491e-04 3.515906e-02
* time: 15.513999938964844
746 7.124895e-04 2.538052e-02
* time: 15.524999856948853
747 7.113318e-04 3.510702e-02
* time: 15.542999982833862
748 7.101756e-04 2.533651e-02
* time: 15.547999858856201
749 7.090213e-04 3.505505e-02
* time: 15.569000005722046
750 7.078686e-04 2.529256e-02
* time: 15.57099986076355
751 7.067176e-04 3.500312e-02
* time: 15.59500002861023
752 7.055683e-04 2.524869e-02
* time: 15.615999937057495
753 7.044208e-04 3.495125e-02
* time: 15.632999897003174
754 7.032749e-04 2.520488e-02
* time: 15.651999950408936
755 7.021307e-04 3.489944e-02
* time: 15.670000076293945
756 7.009882e-04 2.516113e-02
* time: 15.700999975204468
757 6.998474e-04 3.484768e-02
* time: 15.717999935150146
758 6.987083e-04 2.511746e-02
* time: 15.740000009536743
759 6.975709e-04 3.479597e-02
* time: 15.763000011444092
760 6.964351e-04 2.507385e-02
* time: 15.766000032424927
761 6.953011e-04 3.474432e-02
* time: 15.774999856948853
762 6.941687e-04 2.503031e-02
* time: 15.78600001335144
763 6.930380e-04 3.469272e-02
* time: 15.79200005531311
764 6.919090e-04 2.498684e-02
* time: 15.815000057220459
765 6.907817e-04 3.464118e-02
* time: 15.816999912261963
766 6.896559e-04 2.494343e-02
* time: 15.842999935150146
767 6.885320e-04 3.458970e-02
* time: 15.864000082015991
768 6.874096e-04 2.490009e-02
* time: 15.875999927520752
769 6.862890e-04 3.453826e-02
* time: 15.894999980926514
770 6.851699e-04 2.485682e-02
* time: 15.90499997138977
771 6.840526e-04 3.448689e-02
* time: 15.937000036239624
772 6.829369e-04 2.481361e-02
* time: 15.941999912261963
773 6.818229e-04 3.443556e-02
* time: 15.94599986076355
774 6.807104e-04 2.477047e-02
* time: 15.996999979019165
775 6.795998e-04 3.438429e-02
* time: 16.01099991798401
776 6.784906e-04 2.472740e-02
* time: 16.042999982833862
777 6.773832e-04 3.433308e-02
* time: 16.060999870300293
778 6.762774e-04 2.468439e-02
* time: 16.075999975204468
779 6.751733e-04 3.428192e-02
* time: 16.082000017166138
780 6.740708e-04 2.464145e-02
* time: 16.10699987411499
781 6.729700e-04 3.423082e-02
* time: 16.128000020980835
782 6.718707e-04 2.459858e-02
* time: 16.1489999294281
783 6.707731e-04 3.417977e-02
* time: 16.164999961853027
784 6.696771e-04 2.455577e-02
* time: 16.194999933242798
785 6.685829e-04 3.412877e-02
* time: 16.200999975204468
786 6.674901e-04 2.451303e-02
* time: 16.203999996185303
787 6.663991e-04 3.407783e-02
* time: 16.2260000705719
788 6.653096e-04 2.447036e-02
* time: 16.266000032424927
789 6.642218e-04 3.402694e-02
* time: 16.283999919891357
790 6.631356e-04 2.442775e-02
* time: 16.302000045776367
791 6.620511e-04 3.397611e-02
* time: 16.305999994277954
792 6.609681e-04 2.438521e-02
* time: 16.32099986076355
793 6.598868e-04 3.392533e-02
* time: 16.336999893188477
794 6.588070e-04 2.434273e-02
* time: 16.3510000705719
795 6.577289e-04 3.387461e-02
* time: 16.368000030517578
796 6.566523e-04 2.430032e-02
* time: 16.371999979019165
797 6.555775e-04 3.382394e-02
* time: 16.384999990463257
798 6.545041e-04 2.425798e-02
* time: 16.420000076293945
799 6.534324e-04 3.377333e-02
* time: 16.43400001525879
800 6.523623e-04 2.421570e-02
* time: 16.461999893188477
801 6.512938e-04 3.372277e-02
* time: 16.467000007629395
802 6.502269e-04 2.417349e-02
* time: 16.48099994659424
803 6.491616e-04 3.367227e-02
* time: 16.503000020980835
804 6.480978e-04 2.413134e-02
* time: 16.526999950408936
805 6.470357e-04 3.362182e-02
* time: 16.54200005531311
806 6.459752e-04 2.408926e-02
* time: 16.55299997329712
807 6.449162e-04 3.357142e-02
* time: 16.558000087738037
808 6.438588e-04 2.404724e-02
* time: 16.588000059127808
809 6.428031e-04 3.352108e-02
* time: 16.602999925613403
810 6.417488e-04 2.400529e-02
* time: 16.628000020980835
811 6.406962e-04 3.347079e-02
* time: 16.645999908447266
812 6.396451e-04 2.396340e-02
* time: 16.66100001335144
813 6.385956e-04 3.342056e-02
* time: 16.68400001525879
814 6.375477e-04 2.392158e-02
* time: 16.687999963760376
815 6.365014e-04 3.337038e-02
* time: 16.703999996185303
816 6.354565e-04 2.387982e-02
* time: 16.710000038146973
817 6.344134e-04 3.332026e-02
* time: 16.72699999809265
818 6.333717e-04 2.383813e-02
* time: 16.730000019073486
819 6.323316e-04 3.327019e-02
* time: 16.733999967575073
820 6.312930e-04 2.379650e-02
* time: 16.747999906539917
821 6.302561e-04 3.322018e-02
* time: 16.753999948501587
822 6.292206e-04 2.375494e-02
* time: 16.76099991798401
823 6.281868e-04 3.317022e-02
* time: 16.776000022888184
824 6.271544e-04 2.371345e-02
* time: 16.77999997138977
825 6.261237e-04 3.312031e-02
* time: 16.78500008583069
826 6.250944e-04 2.367201e-02
* time: 16.80299997329712
827 6.240668e-04 3.307046e-02
* time: 16.805000066757202
828 6.230406e-04 2.363064e-02
* time: 16.810999870300293
829 6.220160e-04 3.302067e-02
* time: 16.813999891281128
830 6.209930e-04 2.358934e-02
* time: 16.818000078201294
831 6.199715e-04 3.297092e-02
* time: 16.832000017166138
832 6.189514e-04 2.354810e-02
* time: 16.859999895095825
833 6.179330e-04 3.292124e-02
* time: 16.891000032424927
834 6.169161e-04 2.350693e-02
* time: 16.897000074386597
835 6.159007e-04 3.287160e-02
* time: 16.901000022888184
836 6.148868e-04 2.346582e-02
* time: 16.914999961853027
837 6.138745e-04 3.282202e-02
* time: 16.944000005722046
838 6.128636e-04 2.342477e-02
* time: 16.954999923706055
839 6.118544e-04 3.277250e-02
* time: 16.960000038146973
840 6.108466e-04 2.338379e-02
* time: 16.98799991607666
841 6.098403e-04 3.272303e-02
* time: 17.027999877929688
842 6.088356e-04 2.334287e-02
* time: 17.055000066757202
843 6.078324e-04 3.267361e-02
* time: 17.060999870300293
844 6.068306e-04 2.330201e-02
* time: 17.06599998474121
845 6.058304e-04 3.262425e-02
* time: 17.092000007629395
846 6.048317e-04 2.326122e-02
* time: 17.096999883651733
847 6.038345e-04 3.257494e-02
* time: 17.10199999809265
848 6.028388e-04 2.322050e-02
* time: 17.11899995803833
849 6.018446e-04 3.252569e-02
* time: 17.14400005340576
850 6.008519e-04 2.317983e-02
* time: 17.191999912261963
851 5.998607e-04 3.247649e-02
* time: 17.264999866485596
852 5.988710e-04 2.313923e-02
* time: 17.280999898910522
853 5.978828e-04 3.242735e-02
* time: 17.295000076293945
854 5.968960e-04 2.309870e-02
* time: 17.316999912261963
855 5.959108e-04 3.237825e-02
* time: 17.335000038146973
856 5.949270e-04 2.305822e-02
* time: 17.35199999809265
857 5.939448e-04 3.232922e-02
* time: 17.369999885559082
858 5.929640e-04 2.301781e-02
* time: 17.435999870300293
859 5.919847e-04 3.228024e-02
* time: 17.45300006866455
860 5.910069e-04 2.297747e-02
* time: 17.477999925613403
861 5.900306e-04 3.223131e-02
* time: 17.51099991798401
862 5.890557e-04 2.293718e-02
* time: 17.54200005531311
863 5.880823e-04 3.218244e-02
* time: 17.582000017166138
864 5.871104e-04 2.289696e-02
* time: 17.588000059127808
865 5.861400e-04 3.213362e-02
* time: 17.609999895095825
866 5.851710e-04 2.285681e-02
* time: 17.649999856948853
867 5.842035e-04 3.208485e-02
* time: 17.657000064849854
868 5.832374e-04 2.281671e-02
* time: 17.683000087738037
869 5.822728e-04 3.203614e-02
* time: 17.70199990272522
870 5.813097e-04 2.277668e-02
* time: 17.74399995803833
871 5.803480e-04 3.198748e-02
* time: 17.75499987602234
872 5.793878e-04 2.273671e-02
* time: 17.76799988746643
873 5.784291e-04 3.193888e-02
* time: 17.780999898910522
874 5.774717e-04 2.269680e-02
* time: 17.7979998588562
875 5.765159e-04 3.189033e-02
* time: 17.813999891281128
876 5.755615e-04 2.265696e-02
* time: 17.83299994468689
877 5.746085e-04 3.184184e-02
* time: 17.84999990463257
878 5.736570e-04 2.261718e-02
* time: 17.86899995803833
879 5.727070e-04 3.179340e-02
* time: 17.876999855041504
880 5.717583e-04 2.257746e-02
* time: 17.914999961853027
881 5.708111e-04 3.174501e-02
* time: 17.93499994277954
882 5.698653e-04 2.253781e-02
* time: 17.96499991416931
883 5.689211e-04 3.169668e-02
* time: 17.997999906539917
884 5.679781e-04 2.249821e-02
* time: 18.00600004196167
885 5.670367e-04 3.164840e-02
* time: 18.036999940872192
886 5.660967e-04 2.245868e-02
* time: 18.085000038146973
887 5.651581e-04 3.160018e-02
* time: 18.091000080108643
888 5.642209e-04 2.241921e-02
* time: 18.1010000705719
889 5.632852e-04 3.155201e-02
* time: 18.139999866485596
890 5.623508e-04 2.237980e-02
* time: 18.1489999294281
891 5.614179e-04 3.150390e-02
* time: 18.183000087738037
892 5.604864e-04 2.234046e-02
* time: 18.2189998626709
893 5.595564e-04 3.145583e-02
* time: 18.236999988555908
894 5.586277e-04 2.230118e-02
* time: 18.26799988746643
895 5.577005e-04 3.140783e-02
* time: 18.27300000190735
896 5.567746e-04 2.226195e-02
* time: 18.295000076293945
897 5.558502e-04 3.135987e-02
* time: 18.336999893188477
898 5.549272e-04 2.222279e-02
* time: 18.365000009536743
899 5.540056e-04 3.131197e-02
* time: 18.388000011444092
900 5.530854e-04 2.218370e-02
* time: 18.402999877929688
901 5.521666e-04 3.126413e-02
* time: 18.448999881744385
902 5.512492e-04 2.214466e-02
* time: 18.46499991416931
903 5.503332e-04 3.121634e-02
* time: 18.491999864578247
904 5.494185e-04 2.210568e-02
* time: 18.532999992370605
905 5.485054e-04 3.116860e-02
* time: 18.549999952316284
906 5.475935e-04 2.206677e-02
* time: 18.57699990272522
907 5.466831e-04 3.112092e-02
* time: 18.605000019073486
908 5.457740e-04 2.202792e-02
* time: 18.64800000190735
909 5.448664e-04 3.107329e-02
* time: 18.652999877929688
910 5.439601e-04 2.198913e-02
* time: 18.674999952316284
911 5.430552e-04 3.102571e-02
* time: 18.711999893188477
912 5.421517e-04 2.195040e-02
* time: 18.730000019073486
913 5.412496e-04 3.097819e-02
* time: 18.736000061035156
914 5.403488e-04 2.191173e-02
* time: 18.77300000190735
915 5.394494e-04 3.093072e-02
* time: 18.789999961853027
916 5.385514e-04 2.187312e-02
* time: 18.805999994277954
917 5.376548e-04 3.088331e-02
* time: 18.83299994468689
918 5.367595e-04 2.183457e-02
* time: 18.866999864578247
919 5.358656e-04 3.083595e-02
* time: 18.92799997329712
920 5.349731e-04 2.179609e-02
* time: 18.963000059127808
921 5.340819e-04 3.078864e-02
* time: 19.009999990463257
922 5.331921e-04 2.175766e-02
* time: 19.039000034332275
923 5.323037e-04 3.074139e-02
* time: 19.07699990272522
924 5.314166e-04 2.171930e-02
* time: 19.10199999809265
925 5.305309e-04 3.069419e-02
* time: 19.111999988555908
926 5.296465e-04 2.168100e-02
* time: 19.149999856948853
927 5.287635e-04 3.064705e-02
* time: 19.197999954223633
928 5.278818e-04 2.164275e-02
* time: 19.216000080108643
929 5.270015e-04 3.059995e-02
* time: 19.269999980926514
930 5.261225e-04 2.160457e-02
* time: 19.289000034332275
931 5.252449e-04 3.055292e-02
* time: 19.296000003814697
932 5.243686e-04 2.156645e-02
* time: 19.318000078201294
933 5.234937e-04 3.050593e-02
* time: 19.335000038146973
934 5.226201e-04 2.152839e-02
* time: 19.37999987602234
935 5.217479e-04 3.045900e-02
* time: 19.40499997138977
936 5.208770e-04 2.149038e-02
* time: 19.473999977111816
937 5.200074e-04 3.041213e-02
* time: 19.51699995994568
938 5.191391e-04 2.145244e-02
* time: 19.555999994277954
939 5.182722e-04 3.036531e-02
* time: 19.598000049591064
940 5.174066e-04 2.141456e-02
* time: 19.63700008392334
941 5.165424e-04 3.031854e-02
* time: 19.66599988937378
942 5.156795e-04 2.137674e-02
* time: 19.707000017166138
943 5.148179e-04 3.027182e-02
* time: 19.730000019073486
944 5.139576e-04 2.133898e-02
* time: 19.750999927520752
945 5.130986e-04 3.022516e-02
* time: 19.802000045776367
946 5.122410e-04 2.130128e-02
* time: 19.830999851226807
947 5.113847e-04 3.017856e-02
* time: 19.866999864578247
948 5.105297e-04 2.126364e-02
* time: 19.91000008583069
949 5.096760e-04 3.013200e-02
* time: 19.944999933242798
950 5.088236e-04 2.122605e-02
* time: 19.957000017166138
951 5.079725e-04 3.008550e-02
* time: 19.986999988555908
952 5.071228e-04 2.118853e-02
* time: 20.007999897003174
953 5.062743e-04 3.003906e-02
* time: 20.06599998474121
954 5.054272e-04 2.115107e-02
* time: 20.07800006866455
955 5.045813e-04 2.999266e-02
* time: 20.098000049591064
956 5.037368e-04 2.111367e-02
* time: 20.13599991798401
957 5.028936e-04 2.994632e-02
* time: 20.200000047683716
958 5.020516e-04 2.107632e-02
* time: 20.264999866485596
959 5.012110e-04 2.990004e-02
* time: 20.38100004196167
960 5.003716e-04 2.103904e-02
* time: 20.44099998474121
961 4.995336e-04 2.985381e-02
* time: 20.506999969482422
962 4.986968e-04 2.100181e-02
* time: 20.549000024795532
963 4.978613e-04 2.980763e-02
* time: 20.575000047683716
964 4.970271e-04 2.096465e-02
* time: 20.59999990463257
965 4.961942e-04 2.976150e-02
* time: 20.65400004386902
966 4.953626e-04 2.092754e-02
* time: 20.680999994277954
967 4.945323e-04 2.971543e-02
* time: 20.7189998626709
968 4.937032e-04 2.089049e-02
* time: 20.7739999294281
969 4.928755e-04 2.966941e-02
* time: 20.81599998474121
970 4.920489e-04 2.085350e-02
* time: 20.90499997138977
971 4.912237e-04 2.962345e-02
* time: 20.990000009536743
972 4.903998e-04 2.081657e-02
* time: 21.00499987602234
973 4.895771e-04 2.957754e-02
* time: 21.032000064849854
974 4.887557e-04 2.077970e-02
* time: 21.10199999809265
975 4.879356e-04 2.953168e-02
* time: 21.122999906539917
976 4.871167e-04 2.074289e-02
* time: 21.15400004386902
977 4.862991e-04 2.948588e-02
* time: 21.194999933242798
978 4.854827e-04 2.070613e-02
* time: 21.249000072479248
979 4.846677e-04 2.944012e-02
* time: 21.289000034332275
980 4.838538e-04 2.066944e-02
* time: 21.35199999809265
981 4.830413e-04 2.939443e-02
* time: 21.378999948501587
982 4.822300e-04 2.063280e-02
* time: 21.418999910354614
983 4.814199e-04 2.934878e-02
* time: 21.453999996185303
984 4.806111e-04 2.059622e-02
* time: 21.507999897003174
985 4.798036e-04 2.930319e-02
* time: 21.575000047683716
986 4.789973e-04 2.055970e-02
* time: 21.624000072479248
987 4.781923e-04 2.925766e-02
* time: 21.664999961853027
988 4.773884e-04 2.052324e-02
* time: 21.698999881744385
989 4.765859e-04 2.921217e-02
* time: 21.72099995613098
990 4.757846e-04 2.048684e-02
* time: 21.756999969482422
991 4.749845e-04 2.916674e-02
* time: 21.83399987220764
992 4.741857e-04 2.045049e-02
* time: 21.853999853134155
993 4.733881e-04 2.912136e-02
* time: 21.91700005531311
994 4.725917e-04 2.041421e-02
* time: 21.98799991607666
995 4.717966e-04 2.907604e-02
* time: 22.03600001335144
996 4.710027e-04 2.037798e-02
* time: 22.068000078201294
997 4.702101e-04 2.903077e-02
* time: 22.092000007629395
998 4.694187e-04 2.034180e-02
* time: 22.139999866485596
999 4.686285e-04 2.898555e-02
* time: 22.20899987220764
1000 4.678395e-04 2.030569e-02
* time: 22.249000072479248
* Status: failure (reached maximum number of iterations) (line search failed)
* Candidate solution
Minimizer: [1.02e+00, 1.04e+00]
Minimum: 4.678395e-04
* Found with
Algorithm: Gradient Descent
Initial Point: [1.10e+00, 1.10e+00]
* Convergence measures
|x - x'| = 4.17e-05 ≰ 0.0e+00
|x - x'|/|x'| = 3.99e-05 ≰ 0.0e+00
|f(x) - f(x')| = 7.89e-07 ≰ 0.0e+00
|f(x) - f(x')|/|f(x')| = 1.69e-03 ≰ 0.0e+00
|g(x)| = 2.03e-02 ≰ 1.0e-12
* Work counters
Seconds run: 22 (vs limit Inf)
Iterations: 1000
f(x) calls: 2515
∇f(x) calls: 2515
using Pkg
Pkg.add("ForwardDiff")
Updating registry at `C:\Users\slash\.julia\registries\General` Updating git-repo `https://github.com/JuliaRegistries/General.git` [1mFetching: [========================================>] 100.0 %.0 %.6 %.9 % [=====> ] 11.7 %2 %=========> ] 20.0 %==========> ] 23.3 %Fetching: [=============> ] 32.0 %Fetching: [================> ] 38.3 %42.3 % [==================> ] 44.9 % ] 51.3 %======================> ] 52.8 % %3 %0 %.5 %72.1 %Fetching: [==============================> ] 73.9 %.0 %.6 %.2 %> ] 78.1 % [================================> ] 79.3 %Fetching: [====================================> ] 88.4 % [=====================================> ] 91.8 %> ] 94.2 % [=======================================> ] 95.1 %] 97.9 % Resolving package versions... Installed NLSolversBase ────── v7.6.1 Installed OpenBLAS_jll ─────── v0.3.7+5 Installed MutableArithmetics ─ v0.2.2 Updating `C:\Users\slash\.julia\environments\v1.3\Project.toml` [no changes] Updating `C:\Users\slash\.julia\environments\v1.3\Manifest.toml` [d8a4904e] ↑ MutableArithmetics v0.2.1 ⇒ v0.2.2 [d41bc354] ↑ NLSolversBase v7.6.0 ⇒ v7.6.1 [4536629a] ↑ OpenBLAS_jll v0.3.7+4 ⇒ v0.3.7+5
using ForwardDiff
g = x -> ForwardDiff.gradient(rosenbrock, x);
H = x -> ForwardDiff.hessian(rosenbrock, x)
function g!(storage::Vector, x::Vector)
s = g(x)
storage[1:length(s)] = s[1:length(s)]
end
g! (generic function with 1 method)
g([1.0,1.0])
2-element Array{Float64,1}:
-0.0
0.0
res = optimize(rosenbrock, g!,
[0.0, 0.0],
Optim.BFGS(),
Optim.Options(g_tol = 1e-6,
store_trace = true,
show_trace = false))
* Status: success
* Candidate solution
Minimizer: [1.00e+00, 1.00e+00]
Minimum: 7.645684e-21
* Found with
Algorithm: BFGS
Initial Point: [0.00e+00, 0.00e+00]
* Convergence measures
|x - x'| = 3.48e-07 ≰ 0.0e+00
|x - x'|/|x'| = 3.48e-07 ≰ 0.0e+00
|f(x) - f(x')| = 6.91e-14 ≰ 0.0e+00
|f(x) - f(x')|/|f(x')| = 9.03e+06 ≰ 0.0e+00
|g(x)| = 2.32e-09 ≤ 1.0e-06
* Work counters
Seconds run: 0 (vs limit Inf)
Iterations: 16
f(x) calls: 53
∇f(x) calls: 53
@btime res = optimize(rosenbrock, g!,
[0.0, 0.0],
Optim.BFGS(),
Optim.Options(g_tol = 1e-6,
store_trace = true,
show_trace = false))
79.900 μs (876 allocations: 52.00 KiB)
* Status: success
* Candidate solution
Minimizer: [1.00e+00, 1.00e+00]
Minimum: 7.645684e-21
* Found with
Algorithm: BFGS
Initial Point: [0.00e+00, 0.00e+00]
* Convergence measures
|x - x'| = 3.48e-07 ≰ 0.0e+00
|x - x'|/|x'| = 3.48e-07 ≰ 0.0e+00
|f(x) - f(x')| = 6.91e-14 ≰ 0.0e+00
|f(x) - f(x')|/|f(x')| = 9.03e+06 ≰ 0.0e+00
|g(x)| = 2.32e-09 ≤ 1.0e-06
* Work counters
Seconds run: 0 (vs limit Inf)
Iterations: 16
f(x) calls: 53
∇f(x) calls: 53
or $$ \nabla^2 f(x_k) x_{k+1} = \nabla^2 f(x_k) x_k- \nabla f(x_k) $$
function Newton(f::Function, g::Function, h:: Function,
xstart::Vector, verbose::Bool = false,
δ::Float64 = 1e-6, nmax::Int64 = 1000)
k = 1
x = xstart
n = length(x)
δ2 = δ*δ
H = zeros(n,n)+I
dfx = ones(n)
if (verbose)
fx = f(x)
println("$k. x = $x, f(x) = $fx")
end
g(dfx, x)
while (dot(dfx,dfx) > δ2 && k <= nmax)
k += 1
g(dfx,x)
h(H,x)
# Hs = -dfx, x_{k+1} = x_k - s # s = -inv(H)*dfx vs s = -H\dfx
x -= H\dfx # x = x - s
if (verbose)
fx = f(x)
println("$k. x = $x, f(x) = $fx ")
end
end
end
Newton (generic function with 4 methods)
Newton(rosenbrock, rosenbrock_gradient!, rosenbrock_hessian!, [-100.0,100.0], true)
1. x = [-100.0, 100.0], f(x) = 9.801010201e9 2. x = [-99.99994898992475, 9999.989797984948], f(x) = 10200.9896959674 3. x = [0.9999473760899633, -10199.97917119076], f(x) = 1.0405997390386257e10 4. x = [0.9999473761157568, 0.9998947549993318], f(x) = 2.7692731928427748e-9 5. x = [0.9999999999999847, 0.9999999972306961], f(x) = 7.668874361715257e-16 6. x = [1.0, 1.0], f(x) = 0.0 7. x = [1.0, 1.0], f(x) = 0.0
A very basic linesearch implementation skeleton follows.
function ls(f::Function, g::Function, h:: Function,
x0::Vector,
direction::Function, steplength::Function,
δ::Float64 = 1e-6, nmax::Int64 = 1000)
k = 0
x = x0
δ2 = δ*δ
n = length(x)
dfx = ones(n)
g(dfx, x)
# println("$k. $x")
while (dot(dfx,dfx) > δ2 && k <= nmax)
# Compute the search direction
d, dfx = direction(f,g,h,x)
# Compute the step length along d
α = steplength(f,dfx,x,d)
# Update the iterate
x += α*d
k += 1
# println("$k. $x")
end
return x
end
ls (generic function with 3 methods)
constantStep(f::Function, dfx:: Vector, x:: Vector, d::Vector) = 1
constantStep (generic function with 1 method)
n = 3;
Matrix{Float64}(I,n,n)
3×3 Array{Float64,2}:
1.0 0.0 0.0
0.0 1.0 0.0
0.0 0.0 1.0
function direction(f::Function, g:: Function, h:: Function, x::Vector)
n = length(x)
df = ones(n)
H = zeros(n,n)+I
g(df,x)
h(H,x)
return -H\df, df
end
direction (generic function with 1 method)
x = ls(rosenbrock, rosenbrock_gradient!, rosenbrock_hessian!,
[0.0,0.0], direction, constantStep)
2-element Array{Float64,1}:
1.0
1.0
function ArmijoStep(f::Function, dfx::Vector, x::Vector, d:: Vector,
αmax:: Float64 = 1.0, β:: Float64 =0.1, κ:: Float64 =0.2)
s = β*dot(dfx,d)
α = αmax
fx = f(x)
fxcand = f(x+α*d)
while (fxcand >= fx+α*s)
α *= κ
fxcand = f(x+α*d)
end
return α
end
ArmijoStep (generic function with 4 methods)
@btime x =ls(rosenbrock, rosenbrock_gradient!, rosenbrock_hessian!,
[0.0,0.0], direction, ArmijoStep)
18.599 μs (221 allocations: 18.58 KiB)
2-element Array{Float64,1}:
0.9999999999999569
0.9999999999998284
norm(ones(2)-x)
0.0
function direction3(f::Function, g:: Function, h:: Function, x::Vector)
n = length(x)
df = ones(n)
H = zeros(n,n)+I
g(df,x)
h(H,x)
H[1,2] = H[2,1]= 0.0
return -H\df, df
end
direction3 (generic function with 1 method)
ls(rosenbrock, rosenbrock_gradient!, rosenbrock_hessian!,
[0.0,0.0], direction3, ArmijoStep)
2-element Array{Float64,1}:
0.9259531981936803
0.8567279574660482