## on arithmetic derivations of square roots

Posted in Books, Kids, pictures, R, Statistics with tags , , , , , , , , , on November 13, 2020 by xi'an

An intriguing question made a short-lived appearance on the CodeGolf section of Stack Exchange, before being removed, namely the (most concise possible) coding of an arithmetic derivation of the square root of an integer, S, with a 30 digit precision and using only arithmetic operators. I was not aware of the myriad of solutions available, as demonstrated on the dedicated WIkipedia page. And ended playing with three of them during a sleepless pre-election night!

The first solution for finding √S is based on a continued fraction representation of the root,

$\sqrt{S}=a+\cfrac{r}{2a+\cfrac{r}{2a+\ddots}}$

with a²≤S and r=S-a². It is straightforward to code-golf:

while((r<-S-T*T)^2>1e-9)T=(F<-2*T+r/(2*T+F))-T;F


but I found it impossible to reach the 30 digit precision (even when decreasing the error bound from 10⁻⁹). Given the strict rules of the game, this would have been considered to be a failure.

The second solution is Goldschmidt’s algorithm

b=S
T=1/sum((1:S)^2<S)
while((1-S*prod(T)^2)^2>1e-9){
b=b*T[1]^2
T=c((3-b)/2,T)}
S*prod(T)


which is longer for code-golfing but produces both √S and 1/√S (and is faster than the Babylonian method and Newton-Raphson). Again no luck with high precision and almost surely unacceptable for the game.

The third solution is the most interesting [imho] as it mimicks long division, working two digits at a time (and connection with Napier’s bones)

~=length
D=~S
S=c(S,0*(1:30))
p=d=0
a=1:9
while(~S){
F=c(F,x<-sum(a*(20*p+a)<=(g<-100*d+10*S[1]+S[2])))
d=g-x*(20*p+x)
p=x+10*p
S=S[-1:-2]}
sum(10^{1+D/2-1:~F}*F)


plus providing an arbitrary number of digits with no error. This code requires S to be entered as a sequence of digits (with a possible extra top digit 0 to make the integer D even). Returning one digit at a time, it would further have satisfied the constraints of the question (if in a poorly condensed manner).

## not a Bernoulli factory

Posted in Books, Kids, pictures, R with tags , , , , , , , on May 20, 2020 by xi'an

A Riddler riddle I possibly misunderstood:

Four isolated persons are given four fair coins, which can be either flipped once or returned without being flipped. If all flipped coins come up heads, the team wins! Else, if any comes up tails, or if no flip at all is done, it looses. Each person is further given an independent U(0,1) realisation. What is the best strategy?

Since the players are separated, I would presume the same procedure is used by all. Meaning that a coin is tossed with probability p, ie if the uniform is less than p, and untouched otherwise. The probability of winning is then

4(1-p)³p½+6(1-p)³p½²+4(1-p)p³½³+p⁴½⁴

which is maximum for p=0.3420391, with a winning probability of 0.2848424.

solve $$x⌊x⌊x⌊x⌋⌋⌋=2020$$

Where the integral part is the integer immediately below x. Puzzle that I first fail solving by brute force, because I did not look at negative x’s… Since the fourth root of 2020 is between 6 and 7, the solution is either x=6+ε or x=-7+ε, with ε in (0,1). The puzzle then becomes either

$$(6+ε)⌊(6+ε)⌊(6+ε)⌊6+ε⌋⌋⌋ = (6+ε)⌊(6+ε)⌊36+6ε⌋⌋ = (6+ε)⌊(6+ε)(36+⌊6ε⌋)⌋ = 2020$$

where there are 6 possible integer values for $$⌊6ε⌋, with only ⌊6ε⌋=5 being possible, turning the equation into$$

$$(6+ε)⌊41(6+ε)⌋ = (6+ε)(246+⌊41ε⌋) = 2020$$

where again only $$⌊42ε⌋$$=40 being possible, ending up with

$$1716+286ε = 2020$$

which has no solution in (0,1). In the second case

(-7+$$ε$$)$$⌊(-7+ε)⌊(-7+ε)⌊-7+ε⌋⌋⌋$$ = (-7+$$ε$$)$$⌊(-7+ε)(49+⌊-7ε⌋)⌋ = 2020$$

shows that only $$⌊-7ε⌋$$=-3 is possible, leading to

(-7+$$ε$$)$$⌊46(-7+ε))⌋$$ = (-7+$$ε$$) ($$-322+⌊46ε⌋)=2020$$

with only $$⌊46ε⌋$$=17 possible, hence

2135-305$$ε$$=2020

and

$$ε$$=115/305.

A brute force simulated annealing resolution returns x=-6.622706 after 10⁸ iterations. A more interesting question is to figure out the discontinuity points of the function

$$ℵ(x) = x$$$$⌊x⌊x⌊x⌋⌋⌋$$

as they seem to be numerous:

For instance, only 854 of the first 2020 integers enjoy a solution to $$ℵ(x)$$=n.

## stack explode

Posted in Books, Kids, University life with tags , , , , , , , , on October 21, 2019 by xi'an

To say the least, most Stack Exchange communities have been quite active in the past days, not towards solving an unusual flow of questions from new or old users, but in protesting against the exclusion of a moderator who disputed on a moderator forum the relevance of a code of conduct change proposed or imposed by the private company behind Stack Exchange, now called Stack Overflow (like the honomym forum on Stack Exchange). A change about the use of gender pronouns in comments and answers (an announcement that attracted the second largest number of negative votes for the entire site). And an exclusion followed by a sequence of apologies from the company highest officers that did not seem to pacify anyone (first largest number of negative votes!) and that kept the excluded moderator excluded. And leading to close to one hundred moderators resigning or going AWOL. Including one of the most active members of X validated, Glen_b. Who posted a detailed description of the chain of events and a most rational explanation of why he was resigning from being a moderator. And then another major moderator, gung… A flak overflow as put by another report.

“We recognise that Stack Exchange is in no way obliged to take our input. We know that we are guests in the home of a private company. We don’t own the platform, and while we want to help to steer the ship, we don’t have the right to determine how it is governed. What built this network is a sense of community and common purpose, and a big part of that has always been the close relationship and communication between Stack Exchange and stakeholders, such as moderators and users. It’s a shame that we’ve lost something so fundamental.” dearstackexchange.com

What can be learned from this fiasco is that it is not a very good idea to let a technical Q&A forum such as Stack Exchange to be run by a private company. Even though many contributors may have never realised till now this is the case. And even when the company is using A/B tests, Bayesian GLMs, and Stan to decrease the number of “unfriendly comments” on the site. Companies are primarily there to make profit and report to stakeholders, rather than the millions of people contributing to the site for free, sometimes investing a considerable amount of time and energy towards making the questions answered in a constructive manner that benefits the entire audience. Despite the facade coolness as in the nerdy, geeky chatter on the company blog, the company  executives and employees obviously do not share the same goal as the volunteers in the numerous communities of the network. Dealing in public relations rather than sheer exchange and in public image rather than openness and in management rather than empowerment. And in advertising rather than sharing.

Another basic remark is that by growing into so many subjects beyond computer programming, and in particular non-technical topics, the SE platform has hit a stage where some communities goals will inevitably clash with others’. I deem it rather characteristic that the (one?) source of the crisis is the issue of using pronouns as stated by the OP (if any) or else using ungendered pronouns. (Pronouns like they which apparently works in English for both plural and singular—as does you—as early as the 14th century.) As some raised religious arguments against using one or several versions. As well as grammatical ones and further ones of being challenging for some non-native-English speakers. I do not think that a corporate imposition (with threats of exclusionary consequences) one single version of inclusion and tolerance is going to work and especially not within each and all of the communities constituting Stack Exchange, which is why working towards an alternative and decentralised network could be timely.

## another attempt at code golf

Posted in Books, Kids, R with tags , , , on June 12, 2019 by xi'an

I had another lazy weekend go at code golf, trying to code in the most condensed way the following task. Provided with a square matrix A of positive integers, keep iterating the steps

• take the highest square $$𝑥²$$ in A.
• find the smallest adjacent neighbour $$𝑛$$
• replace with x and n with nx

until no square is left (with neighbour defined as either horizontally or vertically and without wrapping around). While I managed a 217 bytes solution, compared with Robin’s 179b improvement, which remains surprising readable!, the puzzle offers two further questions:

1. is there a non-iterative way to find the final matrix B?
2. the puzzle assumes that A satisfies that at each step, the highest square and the smallest neighbour n will be unique, and that the sequence will not repeat forever. Is there a fool-proof way to check this is the case?

## an attempt at code golf

Posted in Kids, R with tags , , , , , , , , , on May 15, 2019 by xi'an

Having discovered codegolf on Stack Exchange a few weeks ago, I spotted a few interesting puzzles since then but only got the opportunity at a try over a quiet and rainy weekend (and Robin being on vacation)! The challenge was to write an R code for deciding whether or not a given integer n is congruent or not, when congruent means that it is the surface of a rectangle triangle with all three sides rational. The question included a pointer to the Birch and Swinnerton-Dyer conjecture as a mean to check congruence although the real solution was provided by Tunnell’s Theorem, which states that n is congruent if and only if the number of integer solutions to 2x²+y²+8z²=n is twice as much as the number of integer solutions to 2x²+y²+32z²=n if n is odd and  the number of integer solutions to 8x²+y²+16z²=n is twice as much as the number of integer solutions to 8x²+y²+64z²=n if n is even. Although this is only true for squared-free integers. (I actually spent more time on figuring out the exact wording of the theorem than on optimising the R code!)

My original solution

p=function(n){
for (i in(n:2)^2)if(n%%i<1)n=n/i
if(n%%2){d=8;f=2;g=16}else{d=2;f=1;g=8}
A=0;b=(-n:n)^2
for(x in d*b)for(y in x+f*b)for(z in g*b)
A=A+(y+z==n)-2*(y+4*z==n)
A==0}


was quite naïve, as shown by the subsequent improvements by senior players, like the final (?) version of Guiseppe:

function(n){b=(-n:n)^2
for(i in b[b>0])n=n/i^(!n%%i)
P=2^(n%%2)
o=outer
!sum(!o(y<-o(8/P*b,2*b,"+")/P-n,z<-16/P*b,"+"),-2*!o(y,4*z,"+"))}


exhibiting a load of code golf tricks, from using an anonymous function to renaming functions with a single letter, to switching from integers to booleans and back with the exclamation mark.