Rosetta Code

Talk:Hofstadter Figure-Figure sequences: Difference between revisions

Page Discussion

Talk:Hofstadter Figure-Figure sequences (view source)

Revision as of 21:34, 3 March 2019

1,881 bytes added ,  5 years ago
m
→‎timings for the REXX solutions: changed verb tense.
m (→‎timings for the REXX solutions: expanded TIME argument. -- ~~~~)
m (→‎timings for the REXX solutions: changed verb tense.)
 
(15 intermediate revisions by 3 users not shown)
Line 18:
:::Not really, this aspect of the definition is present in the references too. I suspect that it may be a part of the original description cited as: D. Hofstadter, "Gödel, Escher, Bach", p. 73, but I don't have it to hand at the moment to check. When I first saw their definition I found it confusing at first too, but that is what made it interesting when trying to code it.
 
::: When I had finished the Python version I checked it with tables of the first 1000 values refered to from Sloane: [http://oeis.org/A005228/b005228.txt here] for R and [http://oeis.org/A005228A030124/b005228b030124.txt here] for S, although the table for S has an off-by-one error. --[[User:Paddy3118|Paddy3118]] 18:31, 22 October 2011 (UTC)
 
::: Another ref. with a similar definition: [http://books.google.co.uk/books?id=aFDWuZZslUUC&pg=PA1385&dq=%22Figure-Figure+sequences%22+Hofstadter,+%22G%C3%B6del,+Escher,+Bach%22,+p.+73&hl=en&ei=cw2jTt7OBMiA8gOD78zYBQ&sa=X&oi=book_result&ct=result&resnum=1&ved=0CDEQ6AEwAA#v=onepage&q&f=false CRC concise encyclopedia of mathematics By Eric W. Weisstein pp 1385]. --[[User:Paddy3118|Paddy3118]] 18:40, 22 October 2011 (UTC)
Line 32:
 
==timings for the REXX solutions==
I normally don't includinginclude timings for the REXX solutions that I post, but when I saw the 2<sup>nd</sup> REXX example's timings, <br>▼
<br>I decided to go back and include the timings here as the REXX 2<sup>nd</sup> example's timings seemed a bit high.▼
 
<br><br>I didn't expect a difference of several orders of magnitude.▼
▲I normally don't including timings for the REXX solutions that I post, but when I saw the 2<sup>nd</sup> REXX example's timings,
<lang rexx>/*REXX pgmprogram to calculatecalculates &and verifies verify the Hofstadter Figure-FigureFigure─Figure sequences. */▼
▲<br>I decided to go back and include the timings here as the 2<sup>nd</sup> example's timings seemed a bit high.
call time 'Reset████████████████████████████████████████████████████████████████████████████████'
▲<br><br>I didn't expect a difference of magnitude.
returnparse _arg x top bot . /*returnobtain theoptional valuearguments tofrom the invokerCL*/▼
▲<lang rexx>/*REXX pgm to calculate & verify the Hofstadter Figure-Figure sequences.*/
if x=='' | x=="," then x= 10 /*Not specified? Then use the default.*/
call time 'Reset'
parseif argtop=='' x| highVtop=="," . then top=1000 /* " /*obtain any C.L." " " " " specifications.*/
if xbot=='' then| xbot=10;="," ifthen highV=bot='' then highV=100040 /*use the" " " " " " defaults?*/
low=1; if x<0 then low=abs(x) /*only display a single │X│ value? /*use unity as the starting point*/
if x<r.=0; r.1=1; then lowrr.=abs(x) r.; rr.1=1; s.=r.; s.1=2 /*onlyinitialize the show aR, singleRR, and │X│S valuearrays.*/
r.errs=0; r.1=1; rr.=r.; rr.1=1 /*initialize the Rnumber of errors found and RR(so arraysfar).*/
s.=0; s.1=2; ss.=s.; ss.2 do i=1low to /*abs(x) " " S " SS/*display the 1st "X values of R & S.*/
say right('R('i") =",20) right(FFR(i),7) right('S('i") =",20) right(FFS(i),7)
errs=0
end do i=low to abs(x) /*show first X values of R & S i*/
say right('R('i") =",20) right(ffr(i),7), /*show nice[↑] list the 1st X Fig─Fig numbers.*/
if x<1 then exit right('S('i") =",20) right(ffs(i),7) /*if X Risn't &positive, Sthen we're done.*/
$.=0 end /*iinitialize the memoization ($) array.*/
do nm=1 for 960bot; sr=ffsFFR(nm); $.r=1 /*calculate 1st the 960first forty S R values.*/▼
say 'took' format(time('Elapsed'),,2) "seconds."
if x<1 then exit end /*m*/ /*stick a[↑] fork in($.) it, we'reis doneused for memoization. */
exit /*stick a[↓] check for duplicate fork#s in it,R we're& done.S*/▼
/*═══════════════════════════════════════verify 1st 1k: unique & present*/
both.=0 do n=1 for top-bot; s=FFS(n) /*initializecalculate the value BOTHof arrayFFS(n). */
if $.s then call ser 'duplicate number in R and S lists:' s; /*build list of 1st 40 R values$.*/s=1
do m=1 for 40; r=ffr(m) end /*n*/ /*calculate 1st[↑] calculate 40the 1st R 960 S values.*/
both.r=1 /*build the BOTH array. /* [↓] check for missing values in R│S*/
do v=1 for top; if \both$.v then call sayErrser 'missing R │ S:' v▼
end /*m*/
end /*v*/ /*build list[↑] are ofall 1st1≤ 960numbers S≤1k values.present?*/
▲ do n=1 for 960; s=ffs(n) /*calculate 1st 960 S values.*/
if both.s then call sayErr 'duplicate number in R and S lists:' s
both.s=1 /*add to the BOTH array. */▼
end /*n*/
/*verify presence and uniqueness.*/▼
do v=1 for highV /*verify all 1 ≤ # ≤ 1k present.*/
▲ if \both.v then call sayErr 'missing R │ S:' v
end /*v*/
say
@vif errs==0 then say 'verification completed for all numbers from 1 ──►'; @i=top " [inclusive]." /*shortcuts to shorten prog width*/
else say @v 'verification failed with' errs "errors."▼
if errs==0 then say @v 'completed for all numbers from 1 ──►' highV @i
say 'and took' format(time('Elapsed█████████████████████████████████████████████████████████████████'),,2) "seconds."
▲ else say @v 'failed with' errs "errors."
▲exit /*verifystick presencea andfork uniquenessin it, we're all done. */
say 'took' format(time('E'),,2) "seconds."
/*──────────────────────────────────────────────────────────────────────────────────────*/
▲exit /*stick a fork in it, we're done.*/
ffrFFR: procedure expose r. s. rr. sss.; parse arg n /*obtain the number from the arguments.*/▼
/*──────────────────────────────────FFR subroutine──────────────────────*/
if r.n\==0 then return r.n /*R.n defined? Then return the value.*/
▲ffr: procedure expose r. s. rr. ss.; parse arg n
if r.n\==0 then return r._=FFR(n-1) + FFS(n-1) /*Defined?calculate Thenthe return theFFR and FFS valuevalues.*/
_=ffr(n-1) + ffs( r.n-1)=_; rr._=1; return _ /*calculateassign the value FFRto R value. & RR; return.*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
r.n=_; rr._=1 /*assign the value to R and RR.*/
ffsFFS: procedure expose r. s. rr. ss.; parse arg n /*search for not null R or S number. */▼
▲return _ /*return the value to the invoker*/
▲ both.if s.n=1 =0 then do k=1 for n /*add to[↓] the 1st BOTH IF array. is a SHORT CIRCUIT. */
/*──────────────────────────────────FFS subroutine──────────────────────*/
if s.k\==0 then if r.k\==0 then iterate /*are both defined?*/
▲ffs: procedure expose r. s. rr. ss.; parse arg n
do call FFR k=1 for n while s.n==0 /*searchdefine for notR.k null via Rthe │ SFFR num. subroutine*/
if s.k\==0 then if ffr(k)\ km=k-1; _=0s.km+1 then iterate /*shortcalc. circuitthe next S number, possibly.*/
km=k-1; _=_+rr._; s.km+1k=_ /*thedefine nextan element SSof number,the possibly S array. */
_=_+rr._ end /*maybe adjust for the FRR num.k*/
return s.n s.k=_; ss._=1 /*definereturn couple of S.n FFS numbersvalue to the invoker. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
end /*k*/
returnser: s.nerrs=errs+1; say '***error***' arg(1); /*return the value to the invoker* return</lang>
'''output''' &nbsp; when using the defaultsdefault inputs:▼
/*──────────────────────────────────SAYERR subroutine───────────────────*/
<pre>
sayErr: errs=errs+1; say; say '***error***!'; say; say arg(1); say; return</lang>
▲'''output''' when using the defaults:
<pre style="overflow:scroll">
R(1) = 1 S(1) = 2
R(2) = 3 S(2) = 4
Line 101 ⟶ 93:
R(9) = 56 S(9) = 13
R(10) = 69 S(10) = 14
took 0.00 seconds.▼
 
verification completed for all numbers from 1 ──► 1000 [inclusive].
 
took 1.58 seconds.
▲and took 0.0022 seconds.
</pre>
The (above) example was run under Windows 7 on aan HPair-gap boxPC (3.2GHz2 GHz) using Regina REXX version 3.9.1.
<br><br>
 
==Formulae hidden to most browsers by under-tested cosmetic edits at 18:19, 28 August 2016 ==
 
Under-tested cosmetic edits made to the task page at 18:19, 28 August 2016, including the injection of spaces around expressions in &lt;math&gt; tags, have left some or all of the task description formulae completely invisible to all browsers which display the graphic file version of formulae rather than processing the MathML (this is, in fact, the majority of browsers). The MediaWiki processor does not currently expect such spaces, and generates syntactically ill-formed HTML if they are introduced. Other aspects of these cosmetic edits may further compound the problem. [[User:Hout|Hout]] ([[User talk:Hout|talk]]) 19:50, 22 September 2016 (UTC)
 
: Visibility of formulae now restored for mainstream browsers like Chrome, IE Edge, Safari, Opera etc [[User:Hout|Hout]] ([[User talk:Hout|talk]]) 12:59, 21 November 2016 (UTC)
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/203386...203402"