NYCJUG/2019-09-10
Beginner's regatta
Andrew Berisha takes a look at an ancient algorithm and how one might implement it in J.
Babylonian Method
Introduction
I was watching a video online: Gerry Sussman - We Really Don't Know How to Compute!
And I found one algorithm that I thought was a good start to learn J with. Gerry called it Heron's method and it can be stated as the following:
We can approximate the square root of a number if we take the number (N), a guess (g) and perform the following:
apprx = (g + N/g)/2
We can feed the approximation into the above algorithm recursively and it will converge to the square root.
Babylonian method in another language
Looking online I found something written in SAS
function BabylonianSqrt(S);
epsilon = 100*constant("maceps"); /* convergence criterion */
if S < 0 then x = .; /* handle negative numbers */
else if S=0 then x = 0; /* handle zero */
else do;
x = BabylonianGuess(S); /* initial guess */
xPrev = 0;
do while (abs(x - xPrev) > epsilon);
xPrev = x;
x = (xPrev + S/xPrev)/2; /* iterate to improve guess */
end;
end;
return( x );
endsub;
quit;
My attempt writing it in J
I knew I wanted to write a verb that would take the value on the left as my N and the right argument as g.
So ideally it would work as 100 bsqr 10 = 10.
Babylonian Method file:///home/aberisha/org/books/herons-method.html 1 of 3 9/9/19, 8:16 PM
I spent quite a lot of time working out the semantics of atop and putting in the right parentheses until I got the following
bsqr=. -:@(([%])+]) 100 bsqr 10 100 bsqr 20
10 12.5
This works when the guess is exactly 10. However, I need to run it recursively to put in any guess. And for the sake of ease, I will put the number I'm finding the square root for as my initial guess. What's pretty cool about this algorithm, by choosing the number as my guess the approximation is half of N.
bsqr=.-:@(([%])+]) 100 bsqr (100 bsqr 100) 100 bsqr (100 bsqr (100 bsqr 100)) 100 bsqr (100 bsqr (100 bsqr (100 bsqr 100))) 100 bsqr (100 bsqr (100 bsqr (100 bsqr (100 bsqr 100)))) 100 bsqr (100 bsqr (100 bsqr (100 bsqr (100 bsqr (100 bsqr 100))))) 100 bsqr (100 bsqr (100 bsqr (100 bsqr (100 bsqr (100 bsqr (100 bsqr 100))))))
We get this result:
26.2401 15.0255 10.8404 10.0326 10.0001 10
This almost works but there has to be a better way. So I searched and found ^:_ which is called converge.
bsqr=.-:@(([%])+]) bsqrt=.] bsqr^:_(]) bsqrt 100 bsqrt 25 bsqrt 2048
10 5 45.2548
After looking at it I turned it into a one-liner by surrounded bsqr with parentheses.
bsqrt=.](-:@(([%])+]))^:_(]
45.2548
I looked at the line some more and was able to introduce the reflex ~ that does something like this: u~ y = y u y. The only thing it can't handle at the moment are negative values.
Author: Andrew Berisha Created: 2019-09-09 Mon 21:14 Validate
bsqr=.-:@(([%])+]) bsqrt=.] bsqr^:_(]) bsqrt 100 bsqrt 25 bsqrt 2048 bsqrt=.](-:@(([%])+]))^:_(]) bsqrt 2048 bsqrt=.(-:@(]+[%]))^:_~
Babylonian Method file:///home/aberisha/org/books/herons-method.html
Show-and-tell
see "Making Pi to Many Digits Easily Accessible in J".
Making Pi to Many Digits Easily Accessible in J
J’s extended-precision integers allows us to represent integers of arbitrary length. Similarly J’s rational number representation allows us to express arbitrarily long non-integers as rational numbers. Though there are any number of ways of calculating a well-known constant like pi to many digits, this has already been done and is available on the web. For instance, this site - http://www.geom.uiuc.edu/~huberty/math5337/groupe/digits.html - gives the first 100,000 digits of pi. Since this many digits is so readily available, how might we store this as a rational number in J? Since we only have a decimal, not a rational, representation easily available we could do something like this:
HIPI=: 31415926535897932384626 … 2541x % 10x^<:100000
If we save this in a file “longPi.ijs”, we find that simply loading it takes a non-trivial amount of time:
6!:2 'load ''c:/amisc/J/NYCJUG/201909/longPi.ijs''' NB. ... % 10x^<:100000 168.704
It takes close to three minutes to load. Let’s see how long it takes to increment this by one.
6!:2 'smoutput >:HIPI' 4141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105559644622948954930381964428810975665933446128475648233786783165271201909145648... 169.307
What about taking the square root?
%:2 1.41421 6!:2 'smoutput %:HIPI' 1.77245 6276.07 0 60 60#:6276.07 1 44 36.07
This took more than an hour and 44 minutes but only gives us the same precision we would get with normal floating point.
%:1p1 1.77245
What if we take the square root another way?
bsqrt=.(-:@(]+[%]))^:_~ bsqrt 2 1.41421
Let’s try it with a much shorter version of the number.
PI100=: 31415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170680x % 10x^<:100 PI100 785398163397448309615660845819875721049292349843776455243736148076954101571552249657008706335529267r25000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 6!:2 'bsqrt 1p1' 3.91532e_5 6!:2 '%: 1p1' 9.5032e_6 6!:2 'bsqrt PI100' C-c C-c C-c C-c C-c C-c C-c C-c C-c C-c C-c C-c|break: bsqrt | bsqrt PI100
This was taking too long. Try an even shorter version of the number.
PI50=: 314159265358979323846264338327950288419716939937510x % 10x^50 >:PI50 41415926535897932384626433832795028841971693993751r10000000000000000000000000000000000000000000000000 6!:2 'ps=. bsqrt PI50' C-c C-c C-c C-c|break: bsqrt |bsqrt[0]
This was taking too long as well. Try an even shorter version of the number.
PI25=: 31415926535897932384626434x % 10x^25 PI25 15707963267948966192313217r5000000000000000000000000 %:PI25 1.77245 6!:2 'ps=. bsqrt PI25' C-c C-c C-c C-c|break: bsqrt |bsqrt[0]
This is still taking too long. Let’s change the square-root routine to take a specified number of iterations.
bsqrt -:@(] + [ % ])^:_~ bsqrt=: -:@(] + [ % ])^:999~ 6!:2 'ps=. bsqrt PI25' C-c C-c C-c C-c|break: bsqrt |bsqrt[0]
This is still taking too long, so let’s do even fewer iterations.
bsqrt=: -:@(] + [ % ])^:99~ 6!:2 'ps=. bsqrt PI25' C-c C-c C-c C-c|break: bsqrt |bsqrt[0]
Still too long – try very few iterations.
bsqrt=: -:@(] + [ % ])^:9~ 6!:2 'ps=. bsqrt PI25' 0.693677 ps 2408939669462590292245864744134331973353074991802353643092537494459396400330534914489683072788635232431938301058172468902322911846600870909458455626209217881092644100847447799187401298152075177497375516534268872649311466931488197038919443370516427227140869... ps^2 5802990331110533772184723145187569262474207883733989884433041860646603606038929791401013663185863457399994846365555503847901147152066294656746196299006734164306779053979271563843032054683774560589654109857358373269753591634504105534115188963229825157246973... 20j18":ps 1.772453850905516027 20j18":%:1p1 1.772453850905515900
This doesn’t give even as many digits as the regular floating point version.
bsqrt=: -:@(] + [ % ])^:20~ 6!:2 'ps=. bsqrt PI25' 25j23":%:1p1 25j23":ps
Advanced topics
This sounds like a classic internet huckster ad but it seems that there is some there there. We look at "The Science-Backed Secret To Rapidly Improving Any Skill".
The Science-Backed Secret To Rapidly Improving Any Skill
Rapid skill improvement is an important part of achieving our most cherished goals. Various scientific research shows us how.
Jude M. King, PhD / Jun 11 · 8 min read
Most of us have significant goals we want to achieve and desires we want to bring to life. But the thing with goals — big or small — is that they often require a lot of learning. Whether it is to write a bestseller, own a profitable business, write viral articles, be a professional software engineer or a great photographer, tons of learning and skill development is involved. How can we learn and improve rapidly to bring our goals to life? What’s the secret to rapid skill improvement?
In their book Art and Fear [1], authors David Bayles and Ted Orland tells the story of a teacher in a pottery class. There’s important lesson to be learnt from this anecdote that reveals the secret to rapid skill improvement, as will be explained in this article. On the first day of the class, the ceramics teacher divided the class into two groups. All those on the left side of the class, he announced, would be graded solely on the quantity of work they produced, all those on the right solely on its quality.
His procedure was simple: on the final day of class he would bring in his bathroom scales and weigh the work of the “quantity” group: fifty pound of pots rated an “A”, forty pounds a “B”, and so on. Those being graded on “quality” however, needed to produce only one pot — albeit a perfect one — to get an “A”.
When grading time came, the results were surprising but emphatic:
The works of highest quality, the most beautiful and creative designs, were all produced by the group graded for quantity.
This interesting anecdote has been retold severally, and the lesson is quite clear: it is quantity that leads to quality.
As Bayles and Orland put it:
It seems that while the quantity group was busily churning out piles of work — and learning from their mistakes — the “quality” group had sat theorizing about perfection, and in the end had little more to show for their efforts than grandiose theories and a pile of dead clay.
The lesson of this story has been reiterated in other similar experiments. An interesting example is the research by Tom Wujec [2] into the “marshmallow problem”— a simple team-building exercise where various groups are given dry spaghetti, a yard of tape and a marshmallow and are asked to build, under time pressure, the tallest tower they can with a marshmallow on top. The result showed that a group of business graduates performed poorly whereas the best performing group was one containing…wait for it…kindergarten kids. The kids not only produced the tallest structures but also the most interesting ones.
So the question was why? How come? What is it about the kids that made them fare better than business school graduates?
To which the answer was, in Tom’s words (emphasis mine):
Business students are trained to find the single right plan…and then they execute on it. They build a tall tower and place the marshmallow on the top as time is running out, only to have the tower collapse under the newly introduced weight. What the kindergartners do differently is that they start with the marshmallow and they build prototypes, successive prototypes always keeping the marshmallow on top, so they have multiple times to fix when they build prototypes along the way.
Interesting, isn’t it?
The lesson in both cases was that it is sub-optimal to sit down theorizing about the best plan or approach rather than getting down to produce a lot of work. Quantity supersedes quality at least when starting out. The people who produce the best work also produce the most work. Thus, quality seems to be what you get after you have produced sufficiently enough. Although these explanation and deductions are perfectly correct. There is an even more interesting explanation which holds the secret to rapid improvement in any skill.
The Learning Feedback Cycle
Improvement is driven by learning. You can’t begin to improve until learning has taken place. That’s obvious. But what’s less obvious is the fact that learning does not automatically lead to improvement. The key to turning learning into improvement is using feedback, which basically means using early results to modify subsequent action(s). There’s a learning feedback cycle and it has three stages [3], according to author Scott Young, namely: input, process and result. The important thing to note here is this:
The feedback cycle is the smallest unit of learning. Therefore, real learning occurs only when all three stages of the feedback cycle is completed. In the pottery example, the “quantity” group completed several of the “learning to make a pot” feedback cycle — input, process and result (the pot) — over the course of the term. Which also meant several units of learning what works and what doesn’t — that drives improvement. Hence the higher quality of their output.
The learning feedback cycle
Their first 5 to 10 pots may have been very mediocre — as is often the case when starting anything new — but focusing on quantity meant every new input in the feedback loop is “richer” than the previous because it included the accumulated knowledge of previous attempts. Thus learning is faster, and skills get developed quicker leading to better output quality. By having a completed pot every now and again, they had that key ingredient that connects learning to improvement: feedback.
On the other hand, the “quality" group’s fixation on making one pristine quality pot rather than making as many as possible and as quickly as possible meant that they completed far less of the learning cycle. Therefore having been denied the key ingredient to improvement — feedback — the quality of their output suffered.
The key lesson here is to realize that no meaningful learning can occur until the learning feedback cycle is completed.
Let’s say, your goal is to write a bestseller. The input stage begins. And the process involves actually sitting down to write, publish and get the book on the marketplace. The result is how your book fared. Did readers judge it good enough? Are they in love with and flock to it as you hoped they would?
A single unit of learning how to write a bestseller, is complete only when you get to the result stage. Completing this book-writing-publishing cycle could take anywhere from 3 months to 10 years…or as long as you make it. The thing to keep in mind is that no real learning occurs until after you shipped and get readers’ feedback.
Does that mean you really don’t learn much about what it takes to write a bestseller while you are still typing away at the keyboard?
Exactly.
This leads to the real key of rapid improvement.
Since improvement comes from learning and real learning does not occur until the feedback cycle is completed. Therefore the key to develop any skill faster is to shorten the feedback cycle.
Getting feedback as quickly as possible is the key to improving any skill quickly. But, also a realization that many people miss.
It’s not always possible to shorten the feedback cycle. Like, when it's impractical to build a business in a few weeks or even months. But given that our tendency is to prioritize analysis over “moving fast and break things", it’s an invaluable lesson to learn.
Timely Feedback Is Critical To Learning
The work of Dr. Anders Ericsson, a professor of psychology who specializes, in the science of peak performance shed light on the importance of timely feedback to learning and improvement. In one research, he observed that surgeon tend to gain skill much faster than general practitioners with the same amount of years of experience. He set out to find why.
The reason, he found, was that surgery tends to give feedback about its success or failure immediately whereas an incorrect diagnosis by a general practitioner could take years to manifest. The surgeon knows immediately what effect his job had while the general practitioner had to wait for several weeks or months before the effect of his diagnosis appear.
For the general practitioner, feedback is slow, and the feedback cycle takes longer to complete. Thus, learning — and improvement — takes longer.
If it takes ten years between starting to write a book and getting it into the hands of your readers, your feedback cycle is at least ten years long! Your learning and improvement will be correspondingly slow. If it’s cut short to weeks or months, your feedback cycle becomes faster and learning and improvement can happen more quickly.
Feedback time is critical to learning. If you want to improve your skills quicker, that’s what you should keep an eye on.
The idea of “quantity over quality” is well-known, but the key behind its efficacy is the length of the feedback cycle. Find a way to shorten your feedback cycle, and you can improve faster in any skill you’re trying to develop.
This is why, as a beginner writer, you’ll learn more about writing and be a better writer overall if you write and publish an article everyday, compared to if you try to write the “perfect article” once a month. In the first case, you publish, get readers feedback, learn what works, what doesn’t, which headline performs better and so on, several times over. Almost all learning works this way. Be it wanting to be programmer, singer, actor, artist, writer, photographer, chef, manager, musician, business person, etc.
The quicker you can go through the feedback cycle the quicker you can learn.
It’s why a huge part of success in anything whether to write viral articles or take great photos is an insistent focus on volume of work/attempt and aggressively use the feedback at each iteration to get better.
Whatever your goal, whatever the skill you are trying to build focusing on going through as many feedback cycle, as quickly as possible is the secret to rapid improvement. Instead of overthinking, over-tweaking and theorizing, show up and do the work. You’ll do better just by trying more and making more attempts. You’ll likely fail more, but you’ll also learn more. Especially when the cost of failure is low — when it’s not brain surgery or piloting an airplane — failing fast is one of the best approach to learning.
Because, the way to get to the masterpiece is often to cycle through several tens and hundreds, aggressively learning what works and what doesn’t.
My strategy has always been: be wrong as fast as we can… which basically means, we’re gonna screw up, let’s just admit that. Let’s not be afraid of that. You can’t get to adulthood before you go through puberty. I won’t get it right the first time, but I will get it wrong really soon, really quickly. — Andrew Stanton.
The secret to doing better is to do more — quicker.
How many pots will you make this week?
Learning and teaching J
see "Prime Parallelograms" and "J's Low-level Obfuscation Leads to Higher Levels of Clarity".
Prime Parallelograms
A few weeks ago I wrote about an interesting graph of numbers recently investigated by the Numberphile crew. We used it as an opportunity to journey into the world of agendas and gerunds by implementing the graph using the J programming language. The second half of that same video outlines another interesting number series which has a similarly interesting implementing in J. Let’s try our hand at plotting it.
Basic Ideas
The basic idea behind calculating the series of numbers in question is to take any positive prime, represent it in base two, reverse the resulting sequence of bits, and subtract the reversed number from the original number in terms of base ten.
Implemented as a tacit, monadic verb in J, this would look something like:
f =: ] - [: #. [: |. #:
Our verb, f, is (=:) the given number (]) minus (-) the base two (#.) of the reverse (|.) of the antibase two (#:) of the given number. We can plot the result of applying f to the first ten thousand primes (p: i. 10000) like so:
require 'plot' 'type dot' plot f"0 p: i. 10000
If we’re feeling especially terse, we could write this as an almost-one-liner by substituting f for our implementation of f:
require 'plot' 'type dot' plot (] - [: #. [: |. #:)"0 p: i. 10000
Implementation
Our implementation of f is a “train of verbs”, which is to say, a collection of verbs that compose together into hooks and forks. We can visualize this composition by looking at the “boxed” representation of our train:
┌─┬─┬──────────────────┐ │]│-│┌──┬──┬──────────┐│ │ │ ││[:│#.│┌──┬──┬──┐││ │ │ ││ │ ││[:│|.│#:│││ │ │ ││ │ │└──┴──┴──┘││ │ │ │└──┴──┴──────────┘│ └─┴─┴──────────────────┘
From right to left, J greedily groups verbs into three verb forks potentially followed by a final two verb hook if the total number of verbs in the train is even. We can see that the first fork, [: |. #:, is a capped fork, which means it’s roughly equivalent to |. @: #:. In the monadic case, this fork takes its argument, converts it to a base two list of ones and zeroes, and reverses that list. Let’s refer to this newly composed verb as a moving forward.
The next fork in our train, [: #. a, is another capped fork building off of our previous fork. Again, this could be expressed using the @: verb to compose #. and a together: #. @: a. In the monadic case, this fork takes its argument, converts it to a reversed binary representation with a, and then converts that reversed list of ones and zero back to base ten with #.. Let’s call this newly composed verb b. Our final fork, ] - b, runs our monadic input through b to get the base ten representation of our reversed binary, and subtracts it from the original argument.
Implicit or Explicit?
If we wanted to make J’s implicit verb training explicit, we could define a, b, and our final f ourselves:
a =: [: |. #: b =: [: #. a f =: ] - b
But why go through all that trouble? Going the explicit route feels like a natural tendency to me, coming from a background of more traditional programming languages, but J’s implicit composition opens up a world of interesting readability properties.
I’m really fascinated by this kind of composition, and I feel like it’s what makes J really unique. I’ll never pass up an opportunity to try implementing something as a train of verbs.
If a man tells a woman he's going to do something, he's going to do it. She doesn't have to remind him every six months. - Tesia Blake
J's Low-level Obfuscation Leads to Higher Levels of Clarity
After reading recent articles by Hillel Wayne [Handwriting Programs in J - https://www.hillelwayne.com/post/handwriting-j/] and Jordan Scales [Hello, J - The Fibonacci Numbers - https://thatjdanisso.cool/j-fibonacci/], I’ve become fascinated with the J programming language. Trying to learn J has opened my mind to new ways of thinking about code.
One of the things I find most interesting about J is its ties to natural language, and its corresponding use of code constructs called “hooks” and “forks”.
Many people argue that J is a “write-only” language because of its extreme terseness and complexity of syntax. As a beginner, I’d tend to agree, but I’m starting to warm up to the idea that it might be more readable than it first lets on [Design Patterns vs. Anti-Patterns in APL - https://www.youtube.com/watch?v=v7Mt0GYHU9A].
What is J?
Other developers far more knowledgable than I have written fantastic introductions to the J programming language. I highly recommend you check out Hillel Wayne’s posts on hand writing programs in J and calculating burn rates in J. Also check out Jordan Scales’ posts on computing the Fibonacci numbers and Pascal’s triangle in J.
If you’re still not inspired, check out this motivating talk on design patterns vs anti-patterns in APL by Aaron Hsu, and watch Tracy Harms wax poetic about the mind-expanding power of consistency and adjacency in the J programming language.
Next be sure to check out the J Primer, J for C Programmers, and Learning J if you’re eager to dive into the nuts and bolts of the language. If you’re only interested in a simple “TL;DR” explanation of J, just know that it’s a high-level, array-oriented programming language that follows in the footsteps of the APL programming language.
Language and J
One of the most interesting aspects of J is that each component of a J expression is associated with a grammatical part of speech.
For example, plain expressions of data like the number five (5), or the list of one through three (1 2 3) are described as nouns. The “plus” operator (+) is a verb because it describes an action that can be applied to a noun. Similarly, the “insert” or “table” modifier (/) is an adverb because it modifies the behavior of a verb.
Unlike the human languages I’m used to, J expressions are evaluated from right to left. The following expression is evaluated as “the result of three plus two, multiplied by five”:
5 * 2 + 3 25
We can modify our + verb with our / adverb to create a new verb that we’ll call “add inserted between”, or more easily, “sum”:
+/ 1 2 3 6
Interestingly, all J verbs can easily operate over different dimensions (or ranks) of data. The + verb will happily and intuitively (in most cases) work on everything from a single atom of data to a many-dimensioned behemoth of a matrix.
Hooks and Forks
In J, any string of two concurrent verbs is called a “hook”, and any string of three concurrent verbs is called a “fork”. Hooks and forks are used to reduce repetition and improve the readability of our code.
Let’s look at a fork:
mean =: +/ % #
Here we’re defining mean to be a verb composed of the “sum” (+/), “divided by” (%), and “tally” (#) verbs. This grouping of three verbs creates a fork. When you pass a single argument into a fork, the two outer verbs (+/ and # in this case) both operate on that argument, and both results are passed as arguments to the middle verb. The resulting value of applying this middle verb is the final result of the fork expression.
A monadic fork applied to a noun.
Let’s use our mean verb to average the numbers one through four:
mean 1 2 3 4 2.5
Just as we’d expect, the average of 1 2 3 4 is 2.5.
Now let’s try our hand at writing a hook. The routing of arguments within a monadic hook are slightly different than our monadic fork. Let’s consider this example:
append_length =: , #
Here we’re defining an append_length verb that first applies “length” (#) to append_length’s argument, and then applies “append” (,) to append_length’s original argument and the result of applying the “length” verb.
A monadic hook applied to a noun.
All that is to say that append_length is a hook that calculates that length of the provided argument and appends it to the end of that argument:
append_length 0 0 1 append_length append_length 0 0 1 2
I highly recommend checking out the guide on forks, hooks, and compound adverbs for a more complete explanation and overview of all the hook and fork forms available to you as a J programmer.