NYCJUG/2022-05-10
Beginner's Regatta
Extended Precision Square Roots
There was recently discussion on the J Forum about calculating square roots in extended precision. The following code is from this essay.
DP=:40 sqrt=: DP&$: : (4 : 0) " 0 assert. 0<:y %/ <.@%: (2 x: (2*x) round y)*10x^2*x+0>.>.10^.y ) round=: DP&$: : (4 : 0) b %~ <.1r2+y*b=. 10x^x )
We see that the first thing assigned is the global variable DP which gives the number of digits past the decimal point we want to get. So, this method does not give unlimited precision. We will see why when we figure out how the sqrt function works.
The first thing to notice is how the header of sqrt binds our global DP as its left argument upon definition. This means that the x value of sqrt is whatever DP was defined as which is 40 in this case.
How sqrt Works
Basically this works by multiplying the number for which we are calculating the root by a large power of 10 with extended precision, giving us a large integer on which we can run the normal square root %: which must special case extended integers because it seems we are able to get arbitrary precision from this method.
Looking at the code, working across this main line from right to left,
%/ <.@%: (2 x: (2*x) round y)*10x^2*x+0>.>.10^.y
Consider just this last part: x+0>.>.10^.y . We see that it is calculating the base 10 logarithm of the right argument y, the number whose root we are taking (2 in this case). The code then adds this log to the right argument, which we know to be fixed at 40 in this case, doubles that then raises (extended precision) 10x to that power. In this case, this gives us 1e84 but with extended precision.
This large power of 10 is multiplied by (2 x: (2*x) round y) - which required me to look up the dyadic form of x: since I was unfamiliar with it. This tells us that the 2 x: form converts its (rational) right argument to numerator, denominator form. For instance:
2 x: 1r2 2r3 4r8 90r100 1 2 2 3 1 2 9 10
We see that it converts a single rational to its lowest form (makes it a proper fraction) numerator and denominator. This gives us two numbers by which we multiply our large power of 10 on the right. Subsequently we take the square root of each of these numbers, round down the result to the nearest integer, giving us two large extended precision integers.
2 x: 80 round 2 2 1 (2 x: 80 round 2)*10x^2*DP+0>.>.10^.2 20000000000000000000000000000000000000000000000000000000000000000000000000000000000 10000000000000000000000000000000000000000000000000000000000000000000000000000000000
Taking the square root (%:) of these and rounding them down to the nearest integer gives us these intermediate results:
<.@%: (2 x: (2*DP) round 2)*10x^2*DP+0>.>.10^.2 141421356237309504880168872420969807856967 100000000000000000000000000000000000000000
It's easy to see that the first number divided by the second one gives us 1.41421356237309504880168872420969807856967.
Note that the "atop" (@) is critical here as the combination of <. and %: without this loses the extended precision and gives floating point results instead:
<.%: (2 x: (2*DP) round 2)*10x^2*DP+0>.>.10^.2 1.41421e41 1e41
A Square-root Solver
Another answer to this problem of extended precision square roots was offered by Mike Day:
From: 'Mike Day' via Programming <programming@jsoftware.com> Date: Thu, Apr 21, 2022 at 6:02 PM Subject: Re: [Jprogramming] Extended precision question To: <programming@jsoftware.com>
One way to obtain high precision roots is to use, say, Newton’s solution to
y = x^2 - a :
Given an estimate x(n-1), the next estimate is
xn = x(n-1) - y/(dy/dx), in Maths notation.
[Implicitly solving dy/dx by using "2" as "+:"]
In J, (J701 on this iPad),
rt =: -:@] + (% +:) NB. x is number whose root is required, y an initial guess 2 rt ^:_] 1. NB. Normal float 1.41421 2 rt ^:(i.5)1x NB. Extended to rational... 1 3r2 17r12 577r408 665857r470832
I forget how I solved this Euler Problem!
Mike
[It should be noted that Mike was at one time the reigning champion of Project Euler]
Show-and-tell
Parsing Recipes
Dan shows us how he put together some J code to parse recipes. The code may be found here: File:Recipe Compare v4.ijs.
]rx_num0=: '^[^0-9]*?([0-9\/\.\- ',fractions1,']+).*' NB. Regular expression to recognize valid numbers
^[^0-9]*?([0-9\/\.\- ¼½¾⅐⅑⅒⅓⅔⅕⅖⅗⅘⅙⅚⅛⅜⅝⅞]+).*
]rx_num1=: '[^0-9]*[0-9',fractions1,']+.*' NB. Regular expression to find units of measure for ingredients
[^0-9]*[0-9¼½¾⅐⅑⅒⅓⅔⅕⅖⅗⅘⅙⅚⅛⅜⅝⅞]+.*
]files0=: {. " 1 fdir inpath, '*.txt'
┌──────────────────┬──────────────────┐
│Rice_Pudding_4.txt│Rice_Pudding_6.txt│
└──────────────────┴──────────────────┘
]files1=: (inpath, ]) each files0
┌────────────────────────────────────────────────────────────────────────────────────────────┬────────────────────────────────────────────────────────────────────────────────────────────┐
│C:\Users\danhi\Documents\computer\J_Users_Group\recipe_parse_compare\data\Rice_Pudding_4.txt│C:\Users\danhi\Documents\computer\J_Users_Group\recipe_parse_compare\data\Rice_Pudding_6.txt│
└────────────────────────────────────────────────────────────────────────────────────────────┴────────────────────────────────────────────────────────────────────────────────────────────┘
]text1=: {{a: -.~ dltb each <;._2 LF,~ CR-.~ (|. ' '; 194 160 { a.) rplc~ y}} each text0
┌───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────...
│┌──────────────────┬───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────...
││Baked Rice Pudding│A warm and delicious Baked Rice Pudding recipe made with cooked rice, cinnamon, and raisins. This simple old-fashioned recipe is easy to m...
│└──────────────────┴───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────...
└───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────...
]text2=: {{y <;.1~ y lce sec_keys}} each text1
┌───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────...
│┌──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────...
││┌───────────┬────────────┬────────────────────────┬───────────┬──────────────────────────┬───────────────────────────┬───────────────────────────────┬────────...
│││Ingredients│4 large eggs│3/4 cup granulated sugar│3 cups milk│1 cup heavy whipping cream│2 teaspoons vanilla extract│1 1/2 teaspoons ground cinnamon│3 cups c...
││└───────────┴────────────┴────────────────────────┴───────────┴──────────────────────────┴───────────────────────────┴───────────────────────────────┴────────...
│└──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────...
└───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────...
]ingredients0=: {{}. ; y #~ ; {{igr_keys lce y}} each y }} each text2
┌───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────...
│┌────────────┬────────────────────────┬───────────┬──────────────────────────┬───────────────────────────┬───────────────────────────────┬─────────────────────...
││4 large eggs│3/4 cup granulated sugar│3 cups milk│1 cup heavy whipping cream│2 teaspoons vanilla extract│1 1/2 teaspoons ground cinnamon│3 cups cooked rice , ...
│└────────────┴────────────────────────┴───────────┴──────────────────────────┴───────────────────────────┴───────────────────────────────┴─────────────────────...
└───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────...
]nrm_units=: ; {{(}. y) ,. ({. y)}} each rx_units0
...
│ fluid ounces │ fluid ounce │
├──────────────┼─────────────┤
│ fl oz │ fluid ounce │
├──────────────┼─────────────┤
│ ounces │ ounce │
├──────────────┼─────────────┤
│ oz │ ounce │
├──────────────┼─────────────┤
│ ml │ milliliter │
├──────────────┼─────────────┤
│ gram │ grams │
├──────────────┼─────────────┤
│ g │ grams │
├──────────────┼─────────────┤
│ kg │ kilogram │
├──────────────┼─────────────┤
│ kilo │ kilogram │
├──────────────┼─────────────┤
│ l │ liter │
└──────────────┴─────────────┘
fread ingredients_src
egg eggs
milk
flour
brown rice
rice malt syrup
rice
brown sugar
powdered sugar
sugar
honey
maple syrup
lemon zest
lemon
almonds almond
butter
vanilla
raisins raisin
cinnamon
nutmeg
cardamom
turmeric
ginger
salt
pepper
cream
walnuts walnut
fruit
rx_ingredients0
┌──────────┬──────┬───────┬────────────┬─────────────────┬──────┬─────────────┬────────────────┬───────┬───────┬─────────────┬────────────┬───────┬─────────────...
│┌───┬────┐│┌────┐│┌─────┐│┌──────────┐│┌───────────────┐│┌────┐│┌───────────┐│┌──────────────┐│┌─────┐│┌─────┐│┌───────────┐│┌──────────┐│┌─────┐│┌───────┬────...
││egg│eggs│││milk│││flour│││brown rice│││rice malt syrup│││rice│││brown sugar│││powdered sugar│││sugar│││honey│││maple syrup│││lemon zest│││lemon│││almonds│almo...
│└───┴────┘│└────┘│└─────┘│└──────────┘│└───────────────┘│└────┘│└───────────┘│└──────────────┘│└─────┘│└─────┘│└───────────┘│└──────────┘│└─────┘│└───────┴────...
└──────────┴──────┴───────┴────────────┴─────────────────┴──────┴─────────────┴────────────────┴───────┴───────┴─────────────┴────────────┴───────┴─────────────...
fread units_src
cup cups
teaspoon teaspoons tsp teas
tablespoon tablespoons tbsp tbs
pound lb
fluid ounce fluid ounces fl oz
ounce ounces oz
each
milliliter ml
grams gram g
kilogram kg kilo
liter l
pinch
dash
can
rx_units0
┌──────────────┬─────────────────────────────────────┬─────────────────────────────────────────┬──────────────┬──────────────────────────────────────┬──────────...
│┌─────┬──────┐│┌──────────┬───────────┬─────┬──────┐│┌────────────┬─────────────┬──────┬─────┐│┌───────┬────┐│┌─────────────┬──────────────┬───────┐│┌───────┬─...
││ cup │ cups │││ teaspoon │ teaspoons │ tsp │ teas │││ tablespoon │ tablespoons │ tbsp │ tbs │││ pound │ lb │││ fluid ounce │ fluid ounces │ fl oz │││ ounce │ ...
│└─────┴──────┘│└──────────┴───────────┴─────┴──────┘│└────────────┴─────────────┴──────┴─────┘│└───────┴────┘│└─────────────┴──────────────┴───────┘│└───────┴─...
└──────────────┴─────────────────────────────────────┴─────────────────────────────────────────┴──────────────┴──────────────────────────────────────┴──────────...
rx_units
(?i)^(.*?)( cup | cups | teaspoon | teaspoons | tsp | teas | tablespoon | tablespoons | tbsp | tbs | pound | lb | fluid ounce | fluid ounces | fl oz | ounce | o...
]ingredients1=: {{ rx_units rxpull ',.'-.~ y}} each each ingredients0
┌───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────...
│┌──┬─────────────────────────────────────────────────────┬───────────────────────────┬─────────────────────────────────────────────────────────┬───────────────...
││┌┐│┌────────────────────────┬───┬─────┬────────────────┐│┌───────────┬─┬──────┬────┐│┌──────────────────────────┬─┬─────┬────────────────────┐│┌──────────────...
││││││3/4 cup granulated sugar│3/4│ cup │granulated sugar│││3 cups milk│3│ cups │milk│││1 cup heavy whipping cream│1│ cup │heavy whipping cream│││2 teaspoons va...
││└┘│└────────────────────────┴───┴─────┴────────────────┘│└───────────┴─┴──────┴────┘│└──────────────────────────┴─┴─────┴────────────────────┘│└──────────────...
│└──┴─────────────────────────────────────────────────────┴───────────────────────────┴─────────────────────────────────────────────────────────┴───────────────...
└───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────...
]foods0=: {{ {. 3}. y}} each each ingredients1
┌──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┬────────...
│┌──┬──────────────────┬──────┬──────────────────────┬─────────────────┬─────────────────┬──────────────────────────────────────────────────┬─────────┐│┌───────...
││┌┐│┌────────────────┐│┌────┐│┌────────────────────┐│┌───────────────┐│┌───────────────┐│┌────────────────────────────────────────────────┐│┌───────┐│││┌──────...
││││││granulated sugar│││milk│││heavy whipping cream│││vanilla extract│││ground cinnamon│││cooked rice cooled (leftover rice works great!)│││raisins│││││whole ...
││└┘│└────────────────┘│└────┘│└────────────────────┘│└───────────────┘│└───────────────┘│└────────────────────────────────────────────────┘│└───────┘│││└──────...
│└──┴──────────────────┴──────┴──────────────────────┴─────────────────┴─────────────────┴──────────────────────────────────────────────────┴─────────┘│└───────...
└──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┴────────...
]foods2=: {{{. 2}. y}} each each foods1
┌─────────────────────────────────────────────────────────────────┬───────────────────────────────────────────────────────────────────────┐
│┌──┬───────┬──────┬───────┬─────────┬──────────┬──────┬─────────┐│┌──────┬───────┬─────────┬──────┬─────────┬──────────┬────────┬───────┐│
││┌┐│┌─────┐│┌────┐│┌─────┐│┌───────┐│┌────────┐│┌────┐│┌───────┐│││┌────┐│┌─────┐│┌───────┐│┌────┐│┌───────┐│┌────────┐│┌──────┐│┌─────┐││
││││││sugar│││milk│││cream│││vanilla│││cinnamon│││rice│││raisins│││││milk│││sugar│││vanilla│││rice│││raisins│││cinnamon│││nutmeg│││cream│││
││└┘│└─────┘│└────┘│└─────┘│└───────┘│└────────┘│└────┘│└───────┘│││└────┘│└─────┘│└───────┘│└────┘│└───────┘│└────────┘│└──────┘│└─────┘││
│└──┴───────┴──────┴───────┴─────────┴──────────┴──────┴─────────┘│└──────┴───────┴─────────┴──────┴─────────┴──────────┴────────┴───────┘│
└─────────────────────────────────────────────────────────────────┴───────────────────────────────────────────────────────────────────────┘
]units0=: {{ {. 2}. y}} each each ingredients1
┌──────────────────────────────────────────────────────────────────────────┬─────────────────────────────────────────────────────────────────────────────────┐
│┌──┬───────┬────────┬───────┬─────────────┬─────────────┬────────┬───────┐│┌────────┬───────┬────────────┬───────┬───────┬────────────┬────────────┬───────┐│
││┌┐│┌─────┐│┌──────┐│┌─────┐│┌───────────┐│┌───────────┐│┌──────┐│┌─────┐│││┌──────┐│┌─────┐│┌──────────┐│┌─────┐│┌─────┐│┌──────────┐│┌──────────┐│┌─────┐││
││││││ cup │││ cups │││ cup │││ teaspoons │││ teaspoons │││ cups │││ cup │││││ cups │││ cup │││ teaspoon │││ cup │││ cup │││ teaspoon │││ teaspoon │││ cup │││
││└┘│└─────┘│└──────┘│└─────┘│└───────────┘│└───────────┘│└──────┘│└─────┘│││└──────┘│└─────┘│└──────────┘│└─────┘│└─────┘│└──────────┘│└──────────┘│└─────┘││
│└──┴───────┴────────┴───────┴─────────────┴─────────────┴────────┴───────┘│└────────┴───────┴────────────┴───────┴───────┴────────────┴────────────┴───────┘│
└──────────────────────────────────────────────────────────────────────────┴─────────────────────────────────────────────────────────────────────────────────┘
]units1=: (nrm_units {{ (y i.~ y,~ {. " 1 x) { (y,~ {: " 1 x) }} ]) each each units0
┌──────────────────────────────────────────────────────────────────────┬────────────────────────────────────────────────────────────────────────────────┐
│┌──┬───────┬───────┬───────┬────────────┬────────────┬───────┬───────┐│┌───────┬───────┬────────────┬───────┬───────┬────────────┬────────────┬───────┐│
││┌┐│┌─────┐│┌─────┐│┌─────┐│┌──────────┐│┌──────────┐│┌─────┐│┌─────┐│││┌─────┐│┌─────┐│┌──────────┐│┌─────┐│┌─────┐│┌──────────┐│┌──────────┐│┌─────┐││
││││││ cup │││ cup │││ cup │││ teaspoon │││ teaspoon │││ cup │││ cup │││││ cup │││ cup │││ teaspoon │││ cup │││ cup │││ teaspoon │││ teaspoon │││ cup │││
││└┘│└─────┘│└─────┘│└─────┘│└──────────┘│└──────────┘│└─────┘│└─────┘│││└─────┘│└─────┘│└──────────┘│└─────┘│└─────┘│└──────────┘│└──────────┘│└─────┘││
│└──┴───────┴───────┴───────┴────────────┴────────────┴───────┴───────┘│└───────┴───────┴────────────┴───────┴───────┴────────────┴────────────┴───────┘│
└──────────────────────────────────────────────────────────────────────┴────────────────────────────────────────────────────────────────────────────────┘
fread fractions_src
/ r
¼ 1r4
½ 1r2
¾ 3r4
⅐ 1r7
⅑ 1r9
⅒ 1r10
⅓ 1r3
⅔ 2r3
⅕ 1r5
⅖ 2r5
⅗ 3r5
⅘ 4r5
⅙ 1r6
⅚ 5r6
⅛ 1r8
⅜ 3r8
⅝ 5r8
⅞ 7r8
-
]fractions=: > {{a: -.~ <;._2 ] TAB,~ y}} each a: -.~ <;._2 ] LF,~ CR -.~ fread fractions_src
┌─┬──────┐
│/│r │
├─┼──────┤
│¼│ 1r4 │
├─┼──────┤
│½│ 1r2 │
├─┼──────┤
│¾│ 3r4 │
├─┼──────┤
│⅐│ 1r7 │
├─┼──────┤
│⅑│ 1r9 │
├─┼──────┤
│⅒│ 1r10 │
├─┼──────┤
│⅓│ 1r3 │
├─┼──────┤
│⅔│ 2r3 │
├─┼──────┤
│⅕│ 1r5 │
├─┼──────┤
│⅖│ 2r5 │
├─┼──────┤
│⅗│ 3r5 │
├─┼──────┤
│⅘│ 4r5 │
├─┼──────┤
│⅙│ 1r6 │
├─┼──────┤
│⅚│ 5r6 │
├─┼──────┤
│⅛│ 1r8 │
├─┼──────┤
│⅜│ 3r8 │
├─┼──────┤
│⅝│ 5r8 │
├─┼──────┤
│⅞│ 7r8 │
├─┼──────┤
│-│ │
└─┴──────┘
{{ {. }. y}} each each ingredients3
┌───────────────────────────────────────────────┬─────────────────────────────────────────┐
│┌────┬──────┬────┬────┬────┬────────┬────┬────┐│┌────┬────┬────┬────┬────┬────┬────┬────┐│
││┌──┐│┌────┐│┌──┐│┌──┐│┌──┐│┌──────┐│┌──┐│┌──┐│││┌──┐│┌──┐│┌──┐│┌──┐│┌──┐│┌──┐│┌──┐│┌──┐││
│││4 │││3/4 │││3 │││1 │││2 │││1 1/2 │││3 │││1 │││││3 │││¼ │││1 │││½ │││¼ │││1 │││¼ │││½ │││
││└──┘│└────┘│└──┘│└──┘│└──┘│└──────┘│└──┘│└──┘│││└──┘│└──┘│└──┘│└──┘│└──┘│└──┘│└──┘│└──┘││
│└────┴──────┴────┴────┴────┴────────┴────┴────┘│└────┴────┴────┴────┴────┴────┴────┴────┘│
└───────────────────────────────────────────────┴─────────────────────────────────────────┘
]amount0=: {{+/ ". y rplc fractions}} each each each {{ {. }. y}} each each ingredients3
┌─────────────────────────────────────┬───────────────────────────────────────────┐
│┌───┬─────┬───┬───┬───┬─────┬───┬───┐│┌───┬─────┬───┬─────┬─────┬───┬─────┬─────┐│
││┌─┐│┌───┐│┌─┐│┌─┐│┌─┐│┌───┐│┌─┐│┌─┐│││┌─┐│┌───┐│┌─┐│┌───┐│┌───┐│┌─┐│┌───┐│┌───┐││
│││4│││3r4│││3│││1│││2│││3r2│││3│││1│││││3│││1r4│││1│││1r2│││1r4│││1│││1r4│││1r2│││
││└─┘│└───┘│└─┘│└─┘│└─┘│└───┘│└─┘│└─┘│││└─┘│└───┘│└─┘│└───┘│└───┘│└─┘│└───┘│└───┘││
│└───┴─────┴───┴───┴───┴─────┴───┴───┘│└───┴─────┴───┴─────┴─────┴───┴─────┴─────┘│
└─────────────────────────────────────┴───────────────────────────────────────────┘
]amount1=: {{7j2 ": y}} each each each amount0
┌─────────────────────────────────────────────────────────────────────────────────┬─────────────────────────────────────────────────────────────────────────────...
│┌─────────┬─────────┬─────────┬─────────┬─────────┬─────────┬─────────┬─────────┐│┌─────────┬─────────┬─────────┬─────────┬─────────┬─────────┬─────────┬──────...
││┌───────┐│┌───────┐│┌───────┐│┌───────┐│┌───────┐│┌───────┐│┌───────┐│┌───────┐│││┌───────┐│┌───────┐│┌───────┐│┌───────┐│┌───────┐│┌───────┐│┌───────┐│┌─────...
│││ 4.00│││ 0.75│││ 3.00│││ 1.00│││ 2.00│││ 1.50│││ 3.00│││ 1.00│││││ 3.00│││ 0.25│││ 1.00│││ 0.50│││ 0.25│││ 1.00│││ 0.25│││ 0....
││└───────┘│└───────┘│└───────┘│└───────┘│└───────┘│└───────┘│└───────┘│└───────┘│││└───────┘│└───────┘│└───────┘│└───────┘│└───────┘│└───────┘│└───────┘│└─────...
│└─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┘│└─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴──────...
└─────────────────────────────────────────────────────────────────────────────────┴─────────────────────────────────────────────────────────────────────────────...
tablesout1
┌───────────────────────────────────────────────────────────────────────────────────────────┬───────────────────────────────────────────────────────────────────...
│┌───┬───────┬───────────┬────────┬────────────────────────────────────────────────────────┐│┌───┬───────┬──────────┬────────┬──────────────────────────────────...
││ │ │ │ │ │││ │ │ │ │ ...
│├───┼───────┼───────────┼────────┼────────────────────────────────────────────────────────┤│├───┼───────┼──────────┼────────┼──────────────────────────────────...
││3 │ 3.00│ cups │rice │3 cups cooked rice , cooled (leftover rice works great!)│││1r2│ 0.50│ cup │rice │½ cup medium-grain white rice, unc...
│├───┼───────┼───────────┼────────┼────────────────────────────────────────────────────────┤│├───┼───────┼──────────┼────────┼──────────────────────────────────...
││ │ │ │ │ │││ │ │ │ │ ...
│├───┼───────┼───────────┼────────┼────────────────────────────────────────────────────────┤│├───┼───────┼──────────┼────────┼──────────────────────────────────...
││ │ │ │ │ │││ │ │ │ │ ...
│├───┼───────┼───────────┼────────┼────────────────────────────────────────────────────────┤│├───┼───────┼──────────┼────────┼──────────────────────────────────...
││3 │ 3.00│ cups │milk │3 cups milk │││3 │ 3.00│ cups │milk │3 cups whole milk ...
│├───┼───────┼───────────┼────────┼────────────────────────────────────────────────────────┤│├───┼───────┼──────────┼────────┼──────────────────────────────────...
││3r4│ 0.75│ cup │sugar │3/4 cup granulated sugar │││1r4│ 0.25│ cup │sugar │¼ cup granulated sugar ...
│├───┼───────┼───────────┼────────┼────────────────────────────────────────────────────────┤│├───┼───────┼──────────┼────────┼──────────────────────────────────...
││1 │ 1.00│ cup │cream │1 cup heavy whipping cream │││1r2│ 0.50│ cup │cream │½ cup heavy cream ...
│├───┼───────┼───────────┼────────┼────────────────────────────────────────────────────────┤│├───┼───────┼──────────┼────────┼──────────────────────────────────...
││2 │ 2.00│ teaspoons │vanilla │2 teaspoons vanilla extract │││1 │ 1.00│ teaspoon │vanilla │1 teaspoon vanilla extract ...
│├───┼───────┼───────────┼────────┼────────────────────────────────────────────────────────┤│├───┼───────┼──────────┼────────┼──────────────────────────────────...
││3r2│ 1.50│ teaspoons │cinnamon│1 1/2 teaspoons ground cinnamon │││1 │ 1.00│ teaspoon │cinnamon│1 teaspoon ground cinnamon ...
│├───┼───────┼───────────┼────────┼────────────────────────────────────────────────────────┤│├───┼───────┼──────────┼────────┼──────────────────────────────────...
││1 │ 1.00│ cup │raisins │1 cup raisins │││1r4│ 0.25│ cup │raisins │¼ cup raisins ...
│├───┼───────┼───────────┼────────┼────────────────────────────────────────────────────────┤│├───┼───────┼──────────┼────────┼──────────────────────────────────...
││ │ │ │ │ │││1r4│ 0.25│ teaspoon │nutmeg │¼ teaspoon ground nutmeg ...
│├───┼───────┼───────────┼────────┼────────────────────────────────────────────────────────┤│├───┼───────┼──────────┼────────┼──────────────────────────────────...
││4 │ 4.00│ │ │4 large eggs │││ │ │ │ │ ...
│└───┴───────┴───────────┴────────┴────────────────────────────────────────────────────────┘│└───┴───────┴──────────┴────────┴──────────────────────────────────...
└───────────────────────────────────────────────────────────────────────────────────────────┴───────────────────────────────────────────────────────────────────...
tablesout2
┌───────────────────────────────────────────────────────────────────────────────────────────┬───────────────────────────────────────────────────────────────────...
│┌───┬───────┬───────────┬────────┬────────────────────────────────────────────────────────┐│┌───┬───────┬──────────┬────────┬──────────────────────────────────...
││3 │ 3.00│ cups │rice │3 cups cooked rice , cooled (leftover rice works great!)│││1r2│ 0.50│ cup │rice │½ cup medium-grain white rice, unc...
│├───┼───────┼───────────┼────────┼────────────────────────────────────────────────────────┤│├───┼───────┼──────────┼────────┼──────────────────────────────────...
││3 │ 3.00│ cups │milk │3 cups milk │││3 │ 3.00│ cups │milk │3 cups whole milk ...
│├───┼───────┼───────────┼────────┼────────────────────────────────────────────────────────┤│├───┼───────┼──────────┼────────┼──────────────────────────────────...
││3r4│ 0.75│ cup │sugar │3/4 cup granulated sugar │││1r4│ 0.25│ cup │sugar │¼ cup granulated sugar ...
│├───┼───────┼───────────┼────────┼────────────────────────────────────────────────────────┤│├───┼───────┼──────────┼────────┼──────────────────────────────────...
││1 │ 1.00│ cup │cream │1 cup heavy whipping cream │││1r2│ 0.50│ cup │cream │½ cup heavy cream ...
│├───┼───────┼───────────┼────────┼────────────────────────────────────────────────────────┤│├───┼───────┼──────────┼────────┼──────────────────────────────────...
││2 │ 2.00│ teaspoons │vanilla │2 teaspoons vanilla extract │││1 │ 1.00│ teaspoon │vanilla │1 teaspoon vanilla extract ...
│├───┼───────┼───────────┼────────┼────────────────────────────────────────────────────────┤│├───┼───────┼──────────┼────────┼──────────────────────────────────...
││3r2│ 1.50│ teaspoons │cinnamon│1 1/2 teaspoons ground cinnamon │││1 │ 1.00│ teaspoon │cinnamon│1 teaspoon ground cinnamon ...
│├───┼───────┼───────────┼────────┼────────────────────────────────────────────────────────┤│├───┼───────┼──────────┼────────┼──────────────────────────────────...
││1 │ 1.00│ cup │raisins │1 cup raisins │││1r4│ 0.25│ cup │raisins │¼ cup raisins ...
│├───┼───────┼───────────┼────────┼────────────────────────────────────────────────────────┤│├───┼───────┼──────────┼────────┼──────────────────────────────────...
││4 │ 4.00│ │ │4 large eggs │││1r4│ 0.25│ teaspoon │nutmeg │¼ teaspoon ground nutmeg ...
│└───┴───────┴───────────┴────────┴────────────────────────────────────────────────────────┘│└───┴───────┴──────────┴────────┴──────────────────────────────────...
└───────────────────────────────────────────────────────────────────────────────────────────┴───────────────────────────────────────────────────────────────────...
tablesout3
┌───────────────────────────────────────────────────────────────────┬──────────────────────────────────────────────────┐
│┌────────┬────────────────────────────────────────────────────────┐│┌────────┬───────────────────────────────────────┐│
││ │ │││ │ ││
│├────────┼────────────────────────────────────────────────────────┤│├────────┼───────────────────────────────────────┤│
││rice │3 cups cooked rice , cooled (leftover rice works great!)│││rice │½ cup medium-grain white rice, uncooked││
│├────────┼────────────────────────────────────────────────────────┤│├────────┼───────────────────────────────────────┤│
││ │ │││ │ ││
│├────────┼────────────────────────────────────────────────────────┤│├────────┼───────────────────────────────────────┤│
││ │ │││ │ ││
│├────────┼────────────────────────────────────────────────────────┤│├────────┼───────────────────────────────────────┤│
││milk │3 cups milk │││milk │3 cups whole milk ││
│├────────┼────────────────────────────────────────────────────────┤│├────────┼───────────────────────────────────────┤│
││sugar │3/4 cup granulated sugar │││sugar │¼ cup granulated sugar ││
│├────────┼────────────────────────────────────────────────────────┤│├────────┼───────────────────────────────────────┤│
││cream │1 cup heavy whipping cream │││cream │½ cup heavy cream ││
│├────────┼────────────────────────────────────────────────────────┤│├────────┼───────────────────────────────────────┤│
││vanilla │2 teaspoons vanilla extract │││vanilla │1 teaspoon vanilla extract ││
│├────────┼────────────────────────────────────────────────────────┤│├────────┼───────────────────────────────────────┤│
││cinnamon│1 1/2 teaspoons ground cinnamon │││cinnamon│1 teaspoon ground cinnamon ││
│├────────┼────────────────────────────────────────────────────────┤│├────────┼───────────────────────────────────────┤│
││raisins │1 cup raisins │││raisins │¼ cup raisins ││
│├────────┼────────────────────────────────────────────────────────┤│├────────┼───────────────────────────────────────┤│
││ │ │││nutmeg │¼ teaspoon ground nutmeg ││
│├────────┼────────────────────────────────────────────────────────┤│├────────┼───────────────────────────────────────┤│
││ │4 large eggs │││ │ ││
│└────────┴────────────────────────────────────────────────────────┘│└────────┴───────────────────────────────────────┘│
└───────────────────────────────────────────────────────────────────┴──────────────────────────────────────────────────┘
Batting Averages
In Knuth, volume 2, the following problem is credited to Bill Gosper:
If a baseball player’s batting average is .334, what is the smallest number of times he has been at bat? [Answer: 287.]
In context, this is solved using continued fractions to find the fraction with smallest denominator in the interval [.3335,.3345]. We are going to use brute force and ignorance to solve the problem for all batting averages .001 to .999. This mainly involves manipulating tables and lists, with the heavy lifting done by J’s key primitive (dyad /.).
A word of baseball explanation: a baseball player has a number of at bats, and may get 0 or 1 hit each at bat. The batting average is (hits)%(at bats) rounded to 3 decimal places.
First note the problem is meaningful: we could achieve any batting average with 1000 at bats, so for any batting average there is a minimum number of at bats. How big can this minimum be? An obvious extreme case is the average .001, representing the interval [.0005,.0015]. Note
%0.0015 666.667 %667 0.00149925
Thus 667 at bats should suffice. We will go through the logic with the maximum number of at bats at 5, and then increase it to 1000, just to be on the safe side. The verb we use for rounding to an integer is
round=:<.@:(0.5&+)
Getting started:
N=:5 AB=:>:i.N t=:round 1000 * AB%/AB AB 1 2 3 4 5 t 1000 500 333 250 200 2000 1000 667 500 400 3000 1500 1000 750 600 4000 2000 1333 1000 800 5000 2500 1667 1250 1000
Here AB is a list of the possible at bats, and t is a table of the averages.
mask=:AB </ AB a=:mask * t mask 0 1 1 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 a 0 500 333 250 200 0 0 667 500 400 0 0 0 750 600 0 0 0 0 800 0 0 0 0 0
Mask is used to zap averages above 1, and the resulting array a contains the averages we want. We match this table of averages with a table of at bats:
ABS=:($ a) $ AB ABS 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5
Now the raveled versions of these tables give us lists of averages and at bats. We can use key (dyad /.) to get what we want. The phrase
(,a)<.//.,ABS
uses averages as keys, at bats as values and uses key with the minimum verb <./ to find the minimum number of at bats for each average. We use nub to label the results:
r=:/:~ (~.,a),.(,a)<.//.,ABS r 0 1 200 5 250 4 333 3 400 5 500 2 600 5 667 3 750 4 800 5
The first column is average, and the second the minimum number of at bats. We can also order on the second column.
s=: r \: {:"1 r
s
200 5
400 5
600 5
800 5
250 4
750 4
333 3
667 3
500 2
0 1
OK, that was with the maximum number of at bats at 5. Let’s increase it to 1000:
N=:1000
AB=:>:i.N
t=:round 1000 * AB%/AB
mask=:AB </ AB
a=:mask * t
ABS=:($ a) $ AB
r=:/:~ (~.,a),.(,a)<.//.,ABS
s=: r \: {:"1 r
10{.r
0 1
1 667
2 401
3 286
4 223
5 182
6 154
7 134
8 118
9 106
10{.s
1 667
999 667
2 401
998 400
499 335
501 335
334 287
666 287
3 286
997 286
We see from this that averages of .001 and .999 require the largest number of at bats, at 667. We also see that we have solved the original problem: the minimum number of at bats for an average of .335 is 287.
Advanced Topics
We look at some attempts to solve one of the crucial aspects for useful multi-threading: mutex. This is a synchronizing mechanism by which we can control threads' exclusive access to data items.
Trying to Multithread
One problem with thread-based multiprocessing is that threads run in the same global address space. This raises issues with how to modify an array if multiple threads are trying to modify it at the same time as well as other resource contention issues.
Suppose that we have a list of files to process and we have several threads running at once to process them all. We might have this list as a table of file names like this:
FLNMS=: >'file1.txt';'file2.txt';'file3.txt';'file4.txt';'file5.txt';'file6.txt'
We could split off a file for processing like this:
'CurrFl FLNMS'=: split FLNMS CurrFl file1.txt FLNMS file2.txt file3.txt file4.txt file5.txt file6.txt
Where split, which comes from stdlib.ijs, splits an array into its first item and the rest of it:
split
{. ,&< }.
This works fine for a single process but what happens if you have multiple threads doing this at the same time?
grab1Flnm=: 3 : '''CurrFl FLNMS''=: split FLNMS' 1 T. '' NB. How many threads we have 5 (grab1Flnm t. '']])&.>i. 1 T. '' NB. Run this once per thread +-+-+-+-+-+ |0|1|2|3|4| +-+-+-+-+-+ CurrFl file5.txt FLNMS file6.txt
Of course the problem here is that each thread assigns CurrFl, each over-writing the one before it, leaving only the most recent value in the global namespace.
Fortunately, we can assign a unique name for each thread using its thread number, the result of 3 T. ''.
Modifying grab1Fl:
grab1Flnm=: 3 : '(nms)=: split FLNMS [ nms=. (''CurrFl'',":3 T. ''''),'' FLNMS'''
This creates a thread-specific name, e.g. CurrFl2 for thread 2. However, this leaves us with a different problem.
FLNMS=: >'file1.txt';'file2.txt';'file3.txt';'file4.txt';'file5.txt';'file6.txt' initFN=: 3 : 'FLNMS=: >''file1.txt'';''file2.txt'';''file3.txt'';''file4.txt'';''file5.txt'';''file6.txt''' (grab1Flnm t. '']])&.>i. 1 T. '' +-+-+-+-+-+ |0|1|2|3|4| +-+-+-+-+-+ 'Curr*' names 0 CurrFl1 CurrFl2 CurrFl3 CurrFl4 CurrFl5 CurrFl1; CurrFl2; CurrFl3; CurrFl4; CurrFl5 +---------+---------+---------+---------+---------+ |file1.txt|file2.txt|file1.txt|file1.txt|file2.txt| +---------+---------+---------+---------+---------+ FLNMS file3.txt file4.txt file5.txt file6.txt
This looks like we only ever got the first two names multiple times. This isn't what we want either.
Trying to use Mutex
It looks like J's multithreading set-up primitive T. offers mutex operations. A mutex is a mutual exclusion object that helps us control which thread is working on a shared resource.
load 'd:/amisc/J/NYCJUG/202205/multiThreading.ijs'
createThreads
3 : '{{ 0 T. '''' }} ^:y]'''''
createThreads 5 NB. Create 5 threads
5
mutex=. 10 T. 0 NB. Create a mutex
mutex
1635749377344
So, a mutex is a special object that looks like a big number in J. Let's try to lock it and unlock it while providing details of what we are doing.
lockMsgUnlock=: 3 : 0
smoutput 'Thread ',(":3 T. ''),' locking at ',":qts''
11 T. y;<5 NB. Maximum 5 second wait
smoutput 'Thread ',(":3 T. ''),' locked at ',":qts''
wait ?5
smoutput 'Thread ',(":3 T. ''),' unlocking at ',":qts''
13 T. y
smoutput 'Thread ',(":3 T. ''),' unlocked at ',":qts''
)
Running it as a plain function uses only our base thread, thread 0:
lockMsgUnlock mutex Thread 0 locking at 2022 5 9 15 57 44.695 Thread 0 locked at 2022 5 9 15 57 44.695 Thread 0 unlocking at 2022 5 9 15 57 47.72 Thread 0 unlocked at 2022 5 9 15 57 47.72
Running it on one of our five threads gives us this:
lockMsgUnlock t. '' mutex Thread 5 locking at 2022 5 9 15 58 26.975 Thread 5 locked at 2022 5 9 15 58 26.976 Thread 5 unlocking at 2022 5 9 15 58 29.989 Thread 5 unlocked at 2022 5 9 15 58 29.989 ++ ++
Now let's try it on two threads sequentially:
lockMsgUnlock t. '' mutex [ lockMsgUnlock t. '' mutex Thread 5 locking at 2022 5 9 15 58 43.318 Thread 5 locked at 2022 5 9 15 58 43.318 Thread 4 locking at 2022 5 9 15 58 43.318 Thread 5 unlocking at 2022 5 9 15 58 44.335 Thread 5 unlocked at 2022 5 9 15 58 44.335 Thread 4 locked at 2022 5 9 15 58 44.335 Thread 4 unlocking at 2022 5 9 15 58 47.353 Thread 4 unlocked at 2022 5 9 15 58 47.353 ++ ++
Problem with Mutex
This looks promising so let's try it on all five threads.
lockMsgUnlock t. '' mutex [ lockMsgUnlock t. '' mutex [ lockMsgUnlock t. '' mutex [ lockMsgUnlock t. '' mutex [ lockMsgUnlock t. '' mutex Thread 1 locking at 2022 5 9 16 3 4.732 Thread 3 locking at 2022 5 9 16 3 4.732 Thread 4 locking at 2022 5 9 16 3 4.732 Thread 2 locking at 2022 5 9 16 3 4.732 Thread 5 locking at 2022 5 9 16 3 4.732 Thread 5 locked at 2022 5 9 16 3 9.007 Thread 4 locked at 2022 5 9 16 3 9.007 Thread 2 locked at 2022 5 9 16 3 9.007 Thread 1 locked at 2022 5 9 16 3 9.007 Thread 3 locked at 2022 5 9 16 3 9.007 Thread 3 unlocking at 2022 5 9 16 3 12.054 Thread 1 unlocking at 2022 5 9 16 3 12.054 Thread 2 unlocking at 2022 5 9 16 3 12.054 |interface error: lockMsgUnlock | 13 T.y |lockMsgUnlock[5]
It started out well with five threads trying to get the lock until thread 5 actually gets it, then thread 4 also gets it which is not right. If we look at where we are stopped, it seems to be on the unlocking part:
13!:1'' |interface error * 13 T.y |lockMsgUnlock[5]
Interestingly, when we look at our thread number, we are not in the base thread 0:
3 T. '' 2
If we turn the debugger off and on again, we get bumped to another thread:
dbr 1 [ dbr 0
|interface error: lockMsgUnlock
|
|lockMsgUnlock[4]
3 T. ''
4
Continuing to do this, we progress through all the threads until we are back to thread 0.
dbr 1 [ dbr 0
|interface error: lockMsgUnlock
|
|lockMsgUnlock[4]
3 T. ''
5
dbr 1 [ dbr 0
|interface error: lockMsgUnlock
|
|lockMsgUnlock[5]
3 T. ''
1
dbr 1 [ dbr 0
|interface error: lockMsgUnlock
|
|lockMsgUnlock[5]
3 T. ''
3
dbr 1 [ dbr 0
|interface error
3 T. ''
0
13!:1''
There is probably something very basic I'm missing here as this mutex does not seem to work as I expected it to. I expected any thread after the first one to lock the mutex to block until it's released.
Trying Mutex Again
When I tried the above again in a new session, I had much better results. I suspect something internal may have gotten corrupted when I was playing around with mutex earlier as it seemed to work fine when I tried again.
MUTEX=: 10 T. 1 NB. This is "recursive" rather than "fast" (0) mutex
lockMsgUnlock t. '' MUTEX [ lockMsgUnlock t. '' MUTEX [ lockMsgUnlock t. '' MUTEX [ lockMsgUnlock t. '' MUTEX [ lockMsgUnlock t. '' MUTEX
Thread 3 locking at 2022 5 9 16 38 20.006
Thread 5 locking at 2022 5 9 16 38 20.006
Thread 1 locking at 2022 5 9 16 38 20.006
Thread 2 locking at 2022 5 9 16 38 20.006
Thread 4 locking at 2022 5 9 16 38 20.006
Thread 5 locked at 2022 5 9 16 38 20.006
Thread 5 unlocking at 2022 5 9 16 38 20.006
Thread 5 unlocked at 2022 5 9 16 38 20.006
Thread 2 locked at 2022 5 9 16 38 20.006
Thread 2 unlocking at 2022 5 9 16 38 20.006
++
++
Thread 2 unlocked at 2022 5 9 16 38 20.006
Thread 4 locked at 2022 5 9 16 38 20.006
Thread 4 unlocking at 2022 5 9 16 38 20.006
Thread 4 unlocked at 2022 5 9 16 38 20.006
Thread 1 locked at 2022 5 9 16 38 20.006
Thread 1 unlocking at 2022 5 9 16 38 20.006
Thread 1 unlocked at 2022 5 9 16 38 20.006
Thread 3 locked at 2022 5 9 16 38 20.006
Thread 3 unlocking at 2022 5 9 16 38 20.006
Thread 3 unlocked at 2022 5 9 16 38 20.006
Removing the current mutex and creating the other kind of mutex, we'll see how it works.
14 T. MUTEX MUTEX 0 MUTEX=: 10 T. 1 NB. "Fast" mutex lockMsgUnlock t. '' MUTEX [ lockMsgUnlock t. '' MUTEX [ lockMsgUnlock t. '' MUTEX [ lockMsgUnlock t. '' MUTEX [ lockMsgUnlock t. '' MUTEX Thread 1 locking at 2022 5 9 16 38 48.891 Thread 3 locking at 2022 5 9 16 38 48.891 Thread 2 locking at 2022 5 9 16 38 48.891 Thread 4 locking at 2022 5 9 16 38 48.891 Thread 5 locking at 2022 5 9 16 38 48.891 Thread 3 locked at 2022 5 9 16 38 48.891 Thread 3 unlocking at 2022 5 9 16 38 48.891 Thread 3 unlocked at 2022 5 9 16 38 48.891 Thread 4 locked at 2022 5 9 16 38 48.891 Thread 4 unlocking at 2022 5 9 16 38 48.891 Thread 4 unlocked at 2022 5 9 16 38 48.891 Thread 5 locked at 2022 5 9 16 38 48.891 Thread 5 unlocking at 2022 5 9 16 38 48.891 Thread 5 unlocked at 2022 5 9 16 38 48.891 Thread 2 locked at 2022 5 9 16 38 48.891 ++ ++ Thread 2 unlocking at 2022 5 9 16 38 48.891 Thread 2 unlocked at 2022 5 9 16 38 48.891 Thread 1 locked at 2022 5 9 16 38 48.891 Thread 1 unlocking at 2022 5 9 16 38 48.891 Thread 1 unlocked at 2022 5 9 16 38 48.891
With no built-in delays, it looks like everything happens in less than 1/1000th of a second.
With this success, let's revisit our routine to hand out unique file names:
grab1Flnm=: 3 : 0
11 T. y NB. Lock mutex
nms=. ('CurrFl',":3 T. ''),' FLNMS'
(nms)=: split FLNMS
13 T. y NB. Release mutex lock
)
grab1Flnm t. '']MUTEX [ grab1Flnm t. '']MUTEX [ grab1Flnm t. '']MUTEX [ grab1Flnm t. '']MUTEX [ grab1Flnm t. '']MUTEX
++
++
'Curr*' names 0
CurrFl1 CurrFl2 CurrFl3 CurrFl4 CurrFl5
CurrFl1;CurrFl2;CurrFl3;CurrFl4;CurrFl5
+---------+---------+---------+---------+---------+
|file4.txt|file2.txt|file5.txt|file3.txt|file1.txt|
+---------+---------+---------+---------+---------+
FLNMS
file6.txt
With this figured out, we can work on some more interesting multi-threading tasks. More about this soon!
Materials
- File:Recipe Compare v4.ijs Dan's recipe parsing code