Rosetta Code

Diophantine linear system solving: Difference between revisions

Page Discussion

Diophantine linear system solving (view source)

Revision as of 14:28, 31 December 2021

1,153 bytes added ,  2 years ago
→‎{{header|Phix}}: updated, added run online link
mNo edit summary
(→‎{{header|Phix}}: updated, added run online link)
Line 868:
 
=={{header|Phix}}==
You can run this online [http://phix.x10.mx/p2js/LLLHnf.htm here].
A mechanical and (no disrespect) somewhat laborious translation of FreeBasic, with a bit of help where needed from the Wren entry.<br>
<!--<lang Phix>(notonlinephixonline)-->▼
(Admittedly made harder by the need to xlate 0 and -1 based idx to 1 based.)▼
▲<!--<lang Phix>(notonline)-->
<span style="color: #000080;font-style:italic;">--
-- demo\rosetta\Diophantine_linear_system_solving.exw
-- ==================================================
--
-- Translation of FreeBasic, with some help from Wren, admittedly made harder
▲(Admittedly made -- harder by the need to xlate 0 and -1 based idx to 1 based.)
--
-- Note that for problem 16 (HMM extended gcd (example 7.2)), the signs of▼
-- the (20) and (37) rows in the null space are flipped, somehow,which I'm told otherwiseis OK.▼
--</span>
<span style="color: #008080;">withoutwith</span> <span style="color: #008080;">jsjavascript_semantics</span> <span style="color: #000080;font-style:italic;">-- (dueusing toan include instead of file readingi/o)</span>
<span style="color: #004080008080;">atominclude</span> <span style="color: #000000;">dbDiophantine_linear_system_constants</span><span style="color: #0000FF;">,.</span> <span style="color: #000000;">lke</span> <span style="color: #0000FF000080;">,</span> <span font-style="color: #000000italic;">lr-- DLS_PROBS/SOLNS</span>▼
<span style="color: #008080;">constant</span> <span style="color: #000000;">echo</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">intext</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">get_textsplit</span><span style="color: #0000FF;">(</span><span style="color: #008000000000;">"Diophantine_linear_system_problems.txt"DLS_PROBS</span><span style="color: #0000FF;">,</span><span style="color: #004600008000;">GT_LF_STRIPPED"\n"</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">outtxt</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">get_textsplit</span><span style="color: #0000FF;">(</span><span style="color: #000000;">DLS_SOLNS</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Diophantine_linear_system_solution.txt\n"</span><span style="color: #0000FF;">,</span><span style="color: #004600;">GT_LF_STRIPPEDfalse</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">nxi</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">nxo</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">input</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000000080;font-style:italic;">/*prompt*/</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">string</span> <span style="color: #7060A8000000;">inin_line</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">intext</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nxi</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">nxi</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">return</span> <span style="color: #7060A8000000;">inin_line</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
Line 892 ⟶ 898:
<span style="color: #008080;">if</span> <span style="color: #000000;">out_line</span> <span style="color: #0000FF;">!=</span> <span style="color: #000000;">expected</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s &lt;&lt;=== expected ***ERROR***\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">expected</span><span style="color: #0000FF;">})</span>
<span style="color: #0000FF;">{}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">wait_key</span><span style="color: #0000FF;">()</span> <span style="color: #000080;font-style:italic;">-- (nb does nowt in a browser)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">nxo</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
Line 914 ⟶ 920:
<span style="color: #004080;">sequence</span> <span style="color: #000000;">a</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">InputABCInputAb_or_c</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">pr</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- input A and b, or a complex constant and compute powers into A</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">pr</span> <span style="color: #008080;">then</span> <span style="color: #000080;font-style:italic;">-- (complex constant)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">m2</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">m1</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span>
Line 921 ⟶ 927:
<span style="color: #004080;">string</span> <span style="color: #000000;">g</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">input</span><span style="color: #0000FF;">(</span><span style="color: #008000;">" a + bi:"</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">rplus</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #008000;">'+'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">g</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">line</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">trim</span><span style="color: #0000FF;">(</span><span style="color: #000000;">g</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">rplus</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">x</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">to_number</span><span style="color: #0000FF;">(</span><span style="color: #000000;">line</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">y</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rplus</span><span style="color: #0000FF;">?</span><span style="color: #7060A8;">to_integer</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">trim</span><span style="color: #0000FF;">(</span><span style="color: #000000;">g</span><span style="color: #0000FF;">[</span><span style="color: #000000;">rplus</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..$])):</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">y</span> <span style="color: #008080;">then</span> <span style="color: #000000;">line</span> <span style="color: #0000FF;">&=</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">" + %g*i"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">output</span><span style="color: #0000FF;">(</span><span style="color: #008000;">" "</span><span style="color: #0000FF;">&</span><span style="color: #000000;">line</span><span style="color: #0000FF;">)</span>
Line 970 ⟶ 976:
<span style="color: #008080;">procedure</span> <span style="color: #000000;">PrntM</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">sw</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">s</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">g</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">line</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">q</span>
Line 994 ⟶ 1,000:
<span style="color: #000000;">sw</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">sw</span> <span style="color: #008080;">and</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">]=</span><span style="color: #000000;">0</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">sw</span> <span style="color: #008080;">then</span> <span style="color: #000000;">g</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #000080;font-style:italic;">-- trivial</span>
<span style="color: #004080;">integersequence</span> <span style="color: #000000;">ilensq</span> <span style="color: #0000FF;">,=</span> <span style="color: #0000007060A8;">krepeat</span><span style="color: #0000FF;">,(</span> <span style="color: #000000008000;">t""</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">tlm</span> <span style="color: #0000FF;">=+</span> <span style="color: #000000;">01</span><span style="color: #0000FF;">)</span>▼
-- Hnf and solution</span>▼
<span style="color: #008080;">for</span> <span style="color: #000000;">rlensq</span><span style="color: #0000FF;">=[</span><span style="color: #000000;">mk</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1]</span> <span style="color: #0080800000FF;">to</span> <span style="color: #000000;">k</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">dog</span>
<span style="color: #000080;font-style:italic;">-- Null space withCalculate lengths squared</span>▼
<span style="color: #000000;">output</span><span style="color: #0000FF;">(</span><span style="color: #000000;">print_row</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">fmts</span><span style="color: #0000FF;">)&</span><span style="color: #008080;">iif</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">=</span><span style="color: #000000;">k</span><span style="color: #0000FF;">?</span><span style="color: #000000;">g</span><span style="color: #0000FF;">:</span><span style="color: #008000;">""</span><span style="color: #0000FF;">))</span>▼
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>▼
▲ <span style="color: #000080;font-style:italic;">-- Null space with lengths squared</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">line</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">print_row</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">fmts</span><span style="color: #0000FF;">)</span>▼
<span style="color: #000000;">q</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">q</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">]*</span><span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">outputlensq</span><span style="color: #0000FF;">([</span><span style="color: #000000;">liner</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">&=</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">" (%d)"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">q</span><span style="color: #0000FF;">))</span>
▲ <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000080;font-style:italic;">-- Hnf and solution and null space</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">order</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">k</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)&</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">k</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
▲ <span style="color: #008080;">for</span> <span style="color: #000000;">liner</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">print_row1</span> <span style="color: #0000FF008080;">(to</span> <span style="color: #000000;">rm</span><span style="color: #0000FF;">,+</span><span style="color: #000000;">fmts1</span> <span style="color: #0000FF008080;">)do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">srr</span> <span style="color: #0000FF;">,=</span> <span style="color: #000000;">sxorder</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">]</span>▼
<span style="color: #000000;">output</span><span style="color: #0000FF;">(</span><span style="color: #000000;">print_row</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rr</span><span style="color: #0000FF;">,</span><span style="color: #000000;">fmts</span><span style="color: #0000FF;">)&</span><span style="color: #000000;">lensq</span><span style="color: #0000FF;">[</span><span style="color: #000000;">rr</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
Line 1,014 ⟶ 1,024:
<span style="color: #008080;">for</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">print_row</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">fmts</span><span style="color: #0000FF;">)&</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- (not particularly helpful:)
-- printf(1,", L:")
-- for s=1 to m+1 do
-- printf(1," %.20g",lambda[r,s])
▲ -- -- Hnf andend solutionfor</span>
<span style="color: #0040807060A8;">atomprintf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lk1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000000000FF;">q)</span>▼
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
Line 1,037 ⟶ 1,053:
<span style="color: #000080;font-style:italic;">-- LLL reduce rows k</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">Reduce</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">)</span>
▲ <span style="color: #004080;">integer</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">sx</span>
▲ <span style="color: #004080;">atom</span> <span style="color: #000000;">lk</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">q</span>
<span style="color: #000000;">col1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">nx</span>
<span style="color: #000000;">col2</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">nx</span>
Line 1,054 ⟶ 1,068:
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">q</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">col1</span><span style="color: #0000FF;"><</span><span style="color: #000000;">nx</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">col1</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]<</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #000000;">Minus</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">q</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">,</span><span style="color: #000000;">col1</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]/</span><span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">col1</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">else</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">lk</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">lambda</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">,</span><span style="color: #000000;">t</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">*</span><span style="color: #7060A8;">abs</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lk</span><span style="color: #0000FF;">)></span><span style="color: #000000;">d</span><span style="color: #0000FF;">[</span><span style="color: #000000;">t</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
<span style="color: #000080;font-style:italic;">-- 2|lambda_kt| &gt; d_t
Line 1,068 ⟶ 1,082:
<span style="color: #008080;">if</span> <span style="color: #000000;">q</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">sx</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iif</span><span style="color: #0000FF;">(</span><span style="color: #000000;">col1</span><span style="color: #0000FF;">=</span><span style="color: #000000;">nx</span><span style="color: #0000FF;">?</span><span style="color: #000000;">m</span><span style="color: #0000FF;">:</span><span style="color: #000000;">mn</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- reduce row k</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">sx</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
Line 1,082 ⟶ 1,096:
<span style="color: #000080;font-style:italic;">-- exchange rows k and k-1</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">Swop</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">rt</span> <span style="color: #0000FF;">,=</span> <span style="color: #000000;">sk</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ttm1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">kt</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span>
▲ <span style="color: #004080;">atom</span> <span style="color: #000000;">db</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">lk</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">lr</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">t</span><span style="color: #0000FF;">]}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">t</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]}</span>
<span style="color: #0000FF004080;">{object</span><span style="color: #000000;">lambda</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ktmp</span><span style="color: #0000FF;">][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">t</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">lambda</span><span style="color: #0000FF;">[</span><span style="color: #000000;">t</span><span style="color: #0000FF;">][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">t</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">lambda</span><span style="color: #0000FF;">[</span><span style="color: #000000;">t</span><span style="color: #0000FF;">][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">t</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">lambda</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">t</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1tm1</span><span style="color: #0000FF;">]}</span>
▲ <span style="color: #000000;">outputlambda</span><span style="color: #0000FF;">([</span><span style="color: #000000;">print_rowt</span><span style="color: #0000FF;">(][</span><span style="color: #000000;">r1</span><span style="color: #0000FF;">,..</span><span style="color: #000000;">fmtstm1</span><span style="color: #0000FF;">)&]</span><span style="color: #008080;">iif</span><span style="color: #0000FF;">(=</span> <span style="color: #000000;">rlambda</span><span style="color: #0000FF;">=[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">?][</span><span style="color: #000000;">g1</span><span style="color: #0000FF;">:..</span><span style="color: #008000000000;">""tm1</span><span style="color: #0000FF;">))]</span>
<span style="color: #000000;">lambda</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">tm1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tmp</span><span style="color: #0000FF;">;</span> <span style="color: #000000;">tmp</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #000080;font-style:italic;">-- update Gram coefficients
-- columns k, k-1 for r &gt; k</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">lk</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">lambda</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">,</span><span style="color: #000000;">t</span><span style="color: #0000FF;">],</span>
<span style="color: #000000;">db</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">[</span><span style="color: #000000;">t</span><span style="color: #0000FF;">]*</span><span style="color: #000000;">d</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">lk</span><span style="color: #0000FF;">*</span><span style="color: #000000;">lk</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">d</span><span style="color: #0000FF;">[</span><span style="color: #000000;">t</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1k</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">=</span><span style="color: #000000;">k</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">lr</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">lambda</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">k</span><span style="color: #0000FF;">],</span>
<span style="color: #000000;">lambda</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]dk1</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]*</span><span style="color: #000000;">lambda</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">t</span><span style="color: #0000FF;">]-</span><span style="color: #000000;">lk</span><span style="color: #0000FF;">*</span><span style="color: #000000;">lr</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">d</span><span style="color: #0000FF;">[</span><span style="color: #000000;">t</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">lambda</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tk</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">dbdk1</span><span style="color: #0000FF;">*</span><span style="color: #000000;">lrlambda</span><span style="color: #0000FF;">+[</span><span style="color: #000000;">lkr</span><span style="color: #0000FF;">*,</span><span style="color: #000000;">lambdat</span><span style="color: #0000FF;">[]-</span><span style="color: #000000;">rlk</span><span style="color: #0000FF;">,*</span><span style="color: #000000;">klr</span><span style="color: #0000FF;">])/</span><span style="color: #000000;">d</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">lambda</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">t</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">db</span><span style="color: #0000FF;">*</span><span style="color: #000000;">lr</span><span style="color: #0000FF;">+</span><span style="color: #000000;">lk</span><span style="color: #0000FF;">*</span><span style="color: #000000;">lambda</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">k</span><span style="color: #0000FF;">])/</span><span style="color: #000000;">dk1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">d</span><span style="color: #0000FF;">[</span><span style="color: #000000;">t</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1k</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">db</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
Line 1,105 ⟶ 1,121:
<span style="color: #000000;">problem_no</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"problem #%d\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">problem_no</span><span style="color: #0000FF;">)</span>
▲ <span style="color: #004080;">integer</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">tl</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">db</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">lk</span>▼
<span style="color: #000000;">InputABCInputAb_or_c</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sw</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- augment Ab~ with column e_m</span>
Line 1,119 ⟶ 1,133:
<span style="color: #008080;">if</span> <span style="color: #000000;">echo</span> <span style="color: #008080;">then</span> <span style="color: #000000;">PrntM</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span>
▲ <span style="color: #004080;">atom</span> <span style="color: #000000;">dbtl</span> <span style="color: #0000FF;">,=</span> <span style="color: #000000;">lk0</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">k</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">m</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span>
<span style="color: #000080;font-style:italic;">-- partial size reduction</span>
<span style="color: #000000;">Reduce</span><span style="color: #0000FF;">(</span><span style="color: #000000;">k</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
Line 1,128 ⟶ 1,143:
<span style="color: #008080;">if</span> <span style="color: #000000;">sw</span> <span style="color: #008080;">then</span>
<span style="color: #000080;font-style:italic;">-- zero rows k-1, k</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">lk</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">lambda</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">t</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #000080;font-style:italic;">-- Lovasz condition
-- Bk &gt;= (alpha - mu_kt^2) * Bt</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">db</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">[</span><span style="color: #000000;">t</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]*</span><span style="color: #000000;">d</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">lk</span><span style="color: #0000FF;">*</span><span style="color: #000000;">lk</span>
<span style="color: #000080;font-style:italic;">-- not satisfied</span>
<span style="color: #000000;">sw</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">db</span><span style="color: #0000FF;">*</span><span style="color: #000000;">ald</span><span style="color: #0000FF;"><</span><span style="color: #000000;">d</span><span style="color: #0000FF;">[</span><span style="color: #000000;">t</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]*</span><span style="color: #000000;">d</span><span style="color: #0000FF;">[</span><span style="color: #000000;">t</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]*</span><span style="color: #000000;">aln</span>
Line 1,202 ⟶ 1,217:
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #0000FF;">?</span><span style="color: #008000;">"done"</span>
<span style="color: #0000FF;">{}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">wait_key</span><span style="color: #0000FF;">()</span>
<!--</lang>-->
▲Note that for problem 16 (HMM extended gcd (example 7.2)), the signs of
▲the (20) and (37) rows in the null space are flipped, somehow, otherwise
output matches that of FreeBasic (and is auto-checked). (I suspect the
issue is FreeBasic distinguishing 0 and -0 in a way that Phix does not)
Eagle eyed viewers may have spotted my blase use of null space there as
if I knew what I was talking about (tee hee).
 
=={{header|Wren}}==
Petelomax
7,794

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/318797"