explicit recursive to tacit

[Martin Kreuzer]

Dear all -

As an exercise I wrote a simple verb which uses recursion:

gftpr=: monad define ("0)
 select. y
  case.  0 do. 0
  case.    do. (y*4) + gftpr y-1
 end.
)

This is what I came up with translating it to tacit:

gftpr=: 0:`(4&*+$:@<:)@.(1&<:)"0 M.

   gftpr i.10
0 4 12 24 40 60 84 112 144 180

By mere accident I found, that /this/ verb (having dropped Times (*))

gftpr=: 0:`(4&+$:@<:)@.(1&<:)"0 M.

gives me the /same/ result.

And this I do not understand.

   jver''
j9.6.0-beta14/j64avx2/windows/commercial/www.jsoftware.com/2024-07-19T02:38:13/clang-18-1-6/SLEEF=1

Any hint welcome.

Thanks.

-Martin

[Marcin Żołek]

I learned about a similar trick a few days ago. The key is how x m&v y works in J.

https://code.jsoftware.com/wiki/Vocabulary/ampm

In your program

gftpr n returns 2n(n+1) where n>=0.

(gftpr n) - (gftpr (n-1)) = 4n

(4&+ $:@<:) n is a hook which executes n (4&+ $:@<:) n which calculates n (4&+) (gftpr (n-1)).

n (4&+) (gftpr (n-1)) is equivalent to 4&+^:n (gftpr (n-1)), so we add 4n to (gftpr (n-1)) and get (gftpr n).

Marcin

To unsubscribe from this group and stop receiving emails from it, send an email to forum+un...@jsoftware.com.

[Jan-Pieter Jacobs]

Hi Martin,

In the first tacit version of gftpr, (4&* + $:@<:) is a fork, called monadically, so 4&* is used as monad.

In the last version of gftpr, (4&+ $:@<:) is a *hook*, used monadically. This means 4&+ is called dyadically, which is equivalent to (4&+@])^:[ which happens to be equivalent to 4&* + ] .

e.g.: 

   2 (4&+) 0

8

   (4&*+]) 5

25

   (4&+]) 5

25

   5 (4&+) 5

25

   5 (4&+@]^:[) 5

25

   +/5,5#4

25

Dyadic bonded verbs are a bit of an oddball in J that might bite you if you're not sure whether verbs are used monadically or dyadically in a sentence.

Hope this helps,

Jan-Pieter

To unsubscribe from this group and stop receiving emails from it, send an email to forum+un...@jsoftware.com.

[Marcin Żołek]

This bite can lead to possibly infinite calculations when performing fixed-point iteration (I did it by mistake last week), for example:

   load ‘trig'

   cos

2&o.

   _ cos 42 NB. linear convergence for all real numbers (solution of the equation cos x = x)

0.739085

   _ sin 42 NB. very slow convergence to 0 (solution of the equation sin x = x)

Convergence to 0 can be seen by for example:

   |. (< 1000) sin 42

This unintuitive trick in J led me to the above discoveries!

Marcin

[Martin Kreuzer]

Hi Jan-Pieter,

Well, what I wanted was a bonded verb used monadically.

Can't recall coming across a dyadic bonded verb deliberately before.

As the line didn't throw an error, I assumed it is a valid expression, but ...

Thanks for the helpful examples. Much clearer now.

-Martin

At 2024-08-01 07:11, you wrote:

Hi Martin,

In the first tacit version of gftpr, (4&* + $:@<:) is a fork, called monadically, so 4&* is used as monad.

In the last version of gftpr, (4&+ $:@<:) is a *hook*, used monadically. This means 4&+ is called dyadically, which is equivalent to (4&+@])^:[ which happens to be equivalent to 4&* + ] .

e.g.:Â

   2 (4&+) 0

8

   (4&*+]) 5

25

   (4&+]) 5

25

   5 (4&+) 5

25

   5 (4&+@]^:[) 5

25

   +/5,5#4

25

Dyadic bonded verbs are a bit of an oddball in J that might bite you if you're not sure whether verbs are used monadically or dyadically in a sentence.

Hope this helps,

Jan-Pieter
On Thu, 1 Aug 2024, 08:28 Martin Kreuzer, <in...@airkreuzer.com> wrote:

Dear all -

As an exercise I wrote a simple verb which uses recursion:

gftpr=: monad define ("0)

 select. y

  case.  0 do. 0

  case.    do. (y*4) + gftpr y-1

 end.

)

This is what I came up with translating it to tacit:

gftpr=: 0:`(4&*+$:@<:)@.(1&<:)"0 M.

   gftpr i.10

0 4 12 24 40 60 84 112 144 180

By mere accident I found, that /this/ verb (having dropped Times (*))

gftpr=: 0:`(4&+$:@<:)@.(1&<:)"0 M.

gives me the /same/ result.

And this I do not understand.

   jver''

j9.6.0-beta14/j64avx2/windows/commercial/ www.jsoftware.com/2024-07-19T02:38:13/clang-18-1-6/SLEEF=1

Any hint welcome.

Thanks.

-Martin

To unsubscribe from this group and stop receiving emails from it, send an email to forum+un...@jsoftware.com.

[Martin Kreuzer]

Hi Marcin -

Thanks for the thorough explanation (regarding dyadic bonded verb).

About your two root finding examples:

I tried some finite numbers (on the left) to understand what they do,
and (with sin) experienced the slow convergence toward zero.

I have never come across a construct as  _ sin 42  before.
- Is that Newton-Raphson in disguise ?
- Any specific reason for argument 42 ?

-Martin

Dear all -

   jver''

j9.6.0-beta14/j64avx2/windows/commercial/ www.jsoftware.com/2024-07-19T02:38:13/clang-18-1-6/SLEEF=1

Any hint welcome.

Thanks.

-Martin

To unsubscribe from this group and stop receiving emails from it, send an email to forum+un...@jsoftware.com.

To unsubscribe from this group and stop receiving emails from it, send an email to forum+un...@jsoftware.com.

[Henry Rich]

The dyadic cases of u&n and m&v have caused more confusion than they are worth.  There is no better definition for them, but since they perform a function that is very rarely called for and are easy to rewrite using ^: we have talked about removing them from the language.  This thread is an argument for the removal.

Henry Rich

[Devon McCormick]

The few times I've used the dyadic form of u&m or m&v, usually by accident, I've been puzzled by the results but have never tried to use them that way for a particular reason.

--

Devon McCormick, CFA

Flâneur

[Marcin Żołek]

   NB. The number 42 is, in The Hitchhiker's Guide to the Galaxy, the

   NB. "Answer to the Ultimate Question of Life, the Universe, and Everything".

   NB. After first iteration of sin or cos we are in [-1 ; 1], so any other real number can be chosen as a starting point in simple iteration.

   NB. Let's take 1 as a starting point this time.

   load 'trig'

   NB. Adverb Iter is defined using modifier trains.

   NB. u Iter is a verb which calculates for each atom of y a pair of boxes:

   NB. fixed point of u found by iteration from input starting point ; number of performed iterations.

   Iter =: ({: ; #)@(^:a:)"0

   NB. Let's begin with simpler example (cos instead of sin).

   NB. Root of f(x) = x - cos x.

   NB. Newton-Raphson method.

   NB. Quadratic convergence.

   (] - (] - cos) % 1 + sin) Iter 1

┌────────┬─┐

│0.739085│5│

└────────┴─┘

   NB. Banach's method (simple iteration).

   NB. Linear convergence.

   cos Iter 1

┌────────┬──┐

│0.739085│77│

└────────┴──┘

   NB. And go back to original case with sin.

   NB. Root of f(x) = x - sin x.

   NB. The root is 0, but the following result is a number close to 0 due to the floating-point arithmetic.

   

   NB. Newton-Raphson method.

   NB. Linear (not quadratic!) convergence, because f'(0) = 1 - cos 0 = 0.

   (] - (] - sin) % 1 - cos) Iter 1

┌──────────┬──┐

│7.29388e_9│45│

└──────────┴──┘

   NB. Simple iteration method.

   NB. The following has slow convergence, because sin x = x - x^3 / 3! + x^5 / 5! - ...

   NB. In other words lim (x -> 0) sin x / x = 1.

   NB. sin Iter 1

   NB. In the book Asymptotic methods in analysis by N. G. de Bruijn there is a proof that

   NB. x_n - x_{n+1} = 0.5 * sqrt(3) * n^(-3/2) + O(n^(-5/2) log n) where x_n is sin^:n x_0 in J notation and 0 < x_0 < PI.

   NB. x_0 is 1 in our case.

   NB. Let's compare the formula from the book with calculations:

   (%: ^&3 <: 1e6) %~ 0.5 * %: 3

8.66027e_10

   -/ _2&{. sin^:(< 1e6) 1

8.66014e_10

   NB. It may be interesting to check the number of iterations in above methods for double-doubles (use 11&c. in J9.6) or change comparison tolerance (9!:19).

Marcin

[Marcin Żołek]

It's worth mentioning that you can find cool illustrations of both of these fixed-point iterations on Wikipedia.

https://en.wikipedia.org/wiki/Fixed-point_iteration

But the coolest thing is that drawing them in J is easy!

   load 'plot trig'

   

   illustrate =: 3 : 0

'r f k x0' =. y

pd 'reset'

pd r ; f

pd (}:@(2&#) ; 0&,@(2&#)@}.) f~^:(< k) x0

pd r ; ']'

pd 'show'

)

   

   illustrate (0 , -: pi) ; 'cos' ; 50 ; 1

   illustrate (0 , -: pi) ; 'sin' ; 50 ; 1

   

Marcin

[Ak]

A few basic demonstrations of your proposed substitutions with ^: or others forms would be useful for me (an unadvanced user), better understand the consequences. 

Thank you in advanced.

Ak

[Henry Rich]

The challenge is to execute the verb u on y, x times, where x is a variable.  Solution: x u@]^:[ y

   (6) >:@]^:[ 5
11

This works for any u.

Long ago we noticed that a bonded verb like

1&+

does not have a useful dyadic definition, because the whole purpose of m& is to convert dyad + into a monad.  So we had the bright idea to x (m&v) y to be (m&v)^:x y:

   (6) 1&+ 5
11

Quite reasonable, except (1) the case is very rare so users don't remember it; (2) they also have to go to the reference material to read it; (3) since (m&v) is almost always intended as a monad, putting it in a dyadic position is almost always a mistake, and a perplexing one.

In other words, the dyadic definition of (m&v) has negative value, and we can improves language by removing it.

Henry Rich

[Jan-Pieter Jacobs]

The only use I could see where m&v would be better than m v@]^:[ would be code-golfing (As recommended by someone here and used in this answer), but that's probably not good enough a reason to keep confusing the rest of us.

Jan-Pieter

[Clifford Reiter]

I use the feature, but I get the way it is a surprise. It took more than a few years for the developers to realize there was an opportunity for a dyadic version of a bonded monad.

I let linear algebra students play with Markov matrices, showing them the results of:

   ]M=: 0.8 0.6 ,: 0.2 0.4

   mp=: +/ . *

    ]I=:=i.2

   M mp M mp M

   3 M&mp I

and then ask leading questions about higher powers etc.

So I use it, but understand the desire to simplify the language.

[Henry Rich]

It will be gone in the next beta (beta-16).  Thanks for being understanding.

Henry Rich

[Jose Mario Quintana]

Playing with J...

   plot ((0.975j_0.1 * ]) + 0.025j0.1 * cos) ^: (i.666) 1
   
   plot ((0.9j0.4 * ]) + 0.1j_0.4 * 2&o.) ^: (i.55) 1
   
   ( Y=. (((0.9j0.4 * ]) + 0.1j_0.4 * 2&o.)^:_) 1 )
_2.4868857j_1.80936134

   (-: cos)  Y
1
   (-: cos) +Y
1

Two cosine fixed points in the complex plane of an apparently infinite number.

[Jose Mario Quintana]

"What goes around comes around" (in a positive sense)

Jforum: Power
https://www.jsoftware.com/pipermail/general/2002-August/009909.html

On Sat, Aug 3, 2024 at 11:59 AM Henry Rich <henry...@gmail.com> wrote:

[Martin Kreuzer]

Hi Marcin -

Regarding 42 :   It's been quite some time ago and therefore I didn't readily make the connection -- which means you made me re-read chapter 27 (and 28, for that matter) to meet Deep Thought again, until 'end of the tape'.

Your  'iter'  adverb has been gratefully accepted and made it into my startup script.

As suggested, I experimented with double-double precision;
- in case of  f(x) = x - cos x  there was no difference (still 5 steps),
- in case of  f(x) = x - sin x ,  after about double the number of iterations
it showed a result about double the order of magnitude closer to zero ...

(I then even managed to unearth the de Bruijn book and looked up the formula you mentioned.)

Thanks for the hints and discussion.

-Martin

At 2024-08-02 20:46, you wrote:

   NB. The number 42 is, in The Hitchhiker's Guide to the Galaxy, the
   NB. "Answer to the Ultimate Question of Life, the Universe, and Everything".
   NB. After first iteration of sin or cos we are in [-1 ; 1], so any other real number can be chosen as a starting point in simple iteration.
   NB. Let's take 1 as a starting point this time.

   load 'trig'


   NB. Adverb Iter is defined using modifier trains.
   NB. u Iter is a verb which calculates for each atom of y a pair of boxes:
   NB. fixed point of u found by iteration from input starting point ; number of performed iterations.
   Iter =: ({: ; #)@(^:a:)"0

   NB. Let's begin with simpler example (cos instead of sin).
   NB. Root of f(x) = x - cos x.

   NB. Newton-Raphson method.
   NB. Quadratic convergence.
   (] - (] - cos) % 1 + sin) Iter 1

┌────────┬─â”
│0.739085│5│
└────────┴─┘

   NB. Banach's method (simple iteration).
   NB. Linear convergence.
   cos Iter 1

┌────────┬──â”
│0.739085│77│
└────────┴──┘

   NB. And go back to original case with sin.
   NB. Root of f(x) = x - sin x.
   NB. The root is 0, but the following result is a number close to 0 due to the floating-point arithmetic.

  
   NB. Newton-Raphson method.
   NB. Linear (not quadratic!) convergence, because f'(0) = 1 - cos 0 = 0.
   (] - (] - sin) % 1 - cos) Iter 1

┌──────────┬──â”
│7.29388e_9│45│
└──────────┴──┘

[Martin Kreuzer]

Thanks -- I enjoyed these (and they are very sensible to parameter changes, very delicate ...).

   _ cos 1       NB. this is from v9.5.2 (gone now)
0.739085
   cos^:_ (1)    NB. this is v9.6.0b16
0.739085
   | (((0.975j_0.1 * ]) + 0.025j0.1 * cos) ^:_) 1
0.739085

-Martin


At 2024-08-04 22:48, you wrote:

Playing with J...

   plot ((0.975j_0.1 * ]) + 0.025j0.1 * cos) ^: (i.666) 1
  Â
   plot ((0.9j0.4 * ]) + 0.1j_0.4 * 2&o.) ^: (i.55) 1
  Â
   ( Y=. (((0.9j0.4 * ]) + 0.1j_0.4 * 2&o.)^:_) 1 )
_2.4868857j_1.80936134

   (-: cos)  Y
1
   (-: cos) +Y

1

Two cosine fixed points in the complex plane of an apparently infinite number.

On Sat, Aug 3, 2024 at 10:23 AM Marcin Żołek < marcin...@students.mimuw.edu.pl> wrote:

It's worth mentioning that you can find cool illustrations of both of these fixed-point iterations on Wikipedia.

https://en.wikipedia.org/wiki/Fixed-point_iteration

But the coolest thing is that drawing them in J is easy!

   load 'plot trig'

  Â

   illustrate =: 3 : 0

'r f k x0' =. y

pd 'reset'

pd r ; f

pd (}:@(2&#) ; 0&,@(2&#)@}.) f~^:(< k) x0

pd r ; ']'

pd 'show'

)

  Â

   illustrate (0 , -: pi) ; 'cos' ; 50 ; 1

   illustrate (0 , -: pi) ; 'sin' ; 50 ; 1

  Â

Marcin

On Aug 2, 2024, at 10:46 PM, Marcin Żołek < marcin...@students.mimuw.edu.pl> wrote:

   NB. The number 42 is, in The Hitchhiker's Guide to the Galaxy, the

   NB. "Answer to the Ultimate Question of Life, the Universe, and Everything".

   NB. After first iteration of sin or cos we are in [-1 ; 1], so any other real number can be chosen as a starting point in simple iteration.

   NB. Let's take 1 as a starting point this time.

   load 'trig'

   NB. Adverb Iter is defined using modifier trains.

   NB. u Iter is a verb which calculates for each atom of y a pair of boxes:

   NB. fixed point of u found by iteration from input starting point ; number of performed iterations.

   Iter =: ({: ; #)@(^:a:)"0

   NB. Let's begin with simpler example (cos instead of sin).

   NB. Root of f(x) = x - cos x.

   NB. Newton-Raphson method.

   NB. Quadratic convergence.

   (] - (] - cos) % 1 + sin) Iter 1

┌────────┬─â”

│0.739085│5│

└────────┴─┘

   NB. Banach's method (simple iteration).

   NB. Linear convergence.

   cos Iter 1

┌────────┬──â”

│0.739085│77│

└────────┴──┘

   NB. And go back to original case with sin.

   NB. Root of f(x) = x - sin x.

   NB. The root is 0, but the following result is a number close to 0 due to the floating-point arithmetic.

  Â

   NB. Newton-Raphson method.

   NB. Linear (not quadratic!) convergence, because f'(0) = 1 - cos 0 = 0.

   (] - (] - sin) % 1 - cos) Iter 1

┌──────────┬──â”

│7.29388e_9│45│

└──────────┴──┘

   NB. Simple iteration method.

   NB. The following has slow convergence, because sin x = x - x^3 / 3! + x^5 / 5! - ...

   NB. In other words lim (x -> 0) sin x / x = 1.

   NB. sin Iter 1

   NB. In the book Asymptotic methods in analysis by N. G. de Bruijn there is a proof that

   NB. x_n - x_{n+1} = 0.5 * sqrt(3) * n^(-3/2) + O(n^(-5/2) log n) where x_n is sin^:n x_0 in J notation and 0 < x_0 < PI.

   NB. x_0 is 1 in our case.

   NB. Let's compare the formula from the book with calculations:

   (%: ^&3 <: 1e6) %~ 0.5 * %: 3

8.66027e_10

   -/ _2&{. sin^:(< 1e6) 1

8.66014e_10

   NB. It may be interesting to check the number of iterations in above methods for double-doubles (use 11&c. in J9.6) or change comparison tolerance (9!:19).

Marcin

On Aug 2, 2024, at 5:21 PM, Martin Kreuzer <in...@airkreuzer.com> wrote:

Hi Marcin -

Thanks for the thorough explanation (regarding dyadic bonded verb).

About your two root finding examples:

I tried some finite numbers (on the left) to understand what they do,

and (with sin) experienced the slow convergence toward zero.

I have never come across a construct as  _ sin 42  before.

- Is that Newton-Raphson in disguise ?

- Any specific reason for argument 42 ?

-Martin

At 2024-08-01 08:15, you wrote:

This bite can lead to possibly infinite calculations when performing fixed-point iteration (I did it by mistake last week), for example:

  load 'trig'

   cos

2&o.

   _ cos 42 NB. linear convergence for all real numbers (solution of the equation cos x = x)

0.739085

   _ sin 42 NB. very slow convergence to 0 (solution of the equation sin x = x)

Convergence to 0 can be seen by for example:

   |. (< 1000) sin 42

This unintuitive trick in J led me to the above discoveries!

Marcin

On Aug 1, 2024, at 9:11 AM, Jan-Pieter Jacobs < janpiete...@gmail.com> wrote:

Hi Martin,

In the first tacit version of gftpr, (4&* + $:@<:) is a fork, called monadically, so 4&* is used as monad.

In the last version of gftpr, (4&+ $:@<:) is a *hook*, used monadically. This means 4&+ is called dyadically, which is equivalent to (4&+@])^:[ which happens to be equivalent to 4&* + ] .

e.g.:

   2 (4&+) 0

8

   (4&*+]) 5

25

   (4&+]) 5

25

   5 (4&+) 5

25

   5 (4&+@]^:[) 5

25

   +/5,5#4

25

Dyadic bonded verbs are a bit of an oddball in J that might bite you if you're not sure whether verbs are used monadically or dyadically in a sentence.

Hope this helps,

Jan-Pieter

On Thu, 1 Aug 2024, 08:28 Martin Kreuzer, <in...@airkreuzer.com> wrote:

Dear all -

As an exercise I wrote a simple verb which uses recursion:

gftpr=: monad define ("0)

 select. y

  case.  0 do. 0

  case.    do. (y*4) + gftpr y-1

 end.

)

This is what I came up with translating it to tacit:

gftpr=: 0:`(4&*+$:@<:)@.(1&<:)"0 M.

   gftpr i.10

0 4 12 24 40 60 84 112 144 180

By mere accident I found, that /this/ verb (having dropped Times (*))

gftpr=: 0:`(4&+$:@<:)@.(1&<:)"0 M.

gives me the /same/ result.

And this I do not understand.

   jver''

j9.6.0-beta14/j64avx2/windows/commercial/ www.jsoftware.com/2024-07-19T02:38:13/clang-18-1-6/SLEEF=1

Any hint welcome.

Thanks.

-Martin

To unsubscribe from this group and stop receiving emails from it, send an email to forum+un...@jsoftware.com.

To unsubscribe from this group and stop receiving emails from it, send an email to forum+un...@jsoftware.com.

To unsubscribe from this group and stop receiving emails from it, send an email to forum+un...@jsoftware.com.

To unsubscribe from this group and stop receiving emails from it, send an email to forum+un...@jsoftware.com.

To unsubscribe from this group and stop receiving emails from it, send an email to forum+un...@jsoftware.com.

[Jose Mario Quintana]

The question 'How many roads must a man walk down?' has also been suggested as having that number as its answer. Having that in mind,

   uu (^:a:)(({: ; #)@)("0)
({: ; #)@(uu^:a:)"0

[Martin Kreuzer]

Hi Marcin -

'A picture is worth a thousand words' -- and, looking at your code, I learned some verbalisations I wasn't aware of.

Thanks.

-Martin

At 2024-08-03 14:22, you wrote:

It's worth mentioning that you can find cool illustrations of both of these fixed-point iterations on Wikipedia.

https://en.wikipedia.org/wiki/Fixed-point_iteration

But the coolest thing is that drawing them in J is easy!

   load 'plot trig'
  
   illustrate =: 3 : 0
'r f k x0' =. y
pd 'reset'
pd r ; f
pd (}:@(2&#) ; 0&,@(2&#)@}.) f~^:(< k) x0
pd r ; ']'
pd 'show'
)
  
   illustrate (0 , -: pi) ; 'cos' ; 50 ; 1
   illustrate (0 , -: pi) ; 'sin' ; 50 ; 1
  
Marcin

On Aug 2, 2024, at 10:46 PM, Marcin Żołek < marcin...@students.mimuw.edu.pl> wrote:

   NB. The number 42 is, in The Hitchhiker's Guide to the Galaxy, the
   NB. "Answer to the Ultimate Question of Life, the Universe, and Everything".
   NB. After first iteration of sin or cos we are in [-1 ; 1], so any other real number can be chosen as a starting point in simple iteration.
   NB. Let's take 1 as a starting point this time.

   load 'trig'


   NB. Adverb Iter is defined using modifier trains.
   NB. u Iter is a verb which calculates for each atom of y a pair of boxes:
   NB. fixed point of u found by iteration from input starting point ; number of performed iterations.
   Iter =: ({: ; #)@(^:a:)"0

   NB. Let's begin with simpler example (cos instead of sin).
   NB. Root of f(x) = x - cos x.

   NB. Newton-Raphson method.
   NB. Quadratic convergence.
   (] - (] - cos) % 1 + sin) Iter 1

┌────────┬─â”
│0.739085│5│
└────────┴─┘

   NB. Banach's method (simple iteration).
   NB. Linear convergence.
   cos Iter 1

┌────────┬──â”
│0.739085│77│
└────────┴──┘

   NB. And go back to original case with sin.
   NB. Root of f(x) = x - sin x.
   NB. The root is 0, but the following result is a number close to 0 due to the floating-point arithmetic.

  
   NB. Newton-Raphson method.
   NB. Linear (not quadratic!) convergence, because f'(0) = 1 - cos 0 = 0.
   (] - (] - sin) % 1 - cos) Iter 1

┌──────────┬──â”
│7.29388e_9│45│
└──────────┴──┘

[Martin Kreuzer]

The twin needed a name proper ...
   reti =: (^:a:)(({: ; #)@)("0)
-M

At 2024-08-20 15:51, you wrote:

The question 'How many roads must a man walk down?' has also been suggested as having that number as its answer. Having that in mind,

   uu (^:a:)(({: ; #)@)("0)

({: ; #)@(uu^:a:)"0




On Tue, Aug 20, 2024 at 6:49 AM Martin Kreuzer <in...@airkreuzer.com> wrote:

Hi Marcin -

Regarding 42 :   It's been quite some time ago and therefore I didn't readily make the connection -- which means you made me re-read chapter 27 (and 28, for that matter) to meet Deep Thought again, until 'end of the tape'.

Your  'iter'  adverb has been gratefully accepted and made it into my startup script.

As suggested, I experimented with double-double precision;

- in case of  f(x) = x - cos x  there was no difference (still 5 steps),

- in case of  f(x) = x - sin x ,  after about double the number of iterations

it showed a result about double the order of magnitude closer to zero ...

(I then even managed to unearth the de Bruijn book and looked up the formula you mentioned.)

Thanks for the hints and discussion.

-Martin

At 2024-08-02 20:46, you wrote:

   NB. The number 42 is, in The Hitchhiker's Guide to the Galaxy, the

   NB. "Answer to the Ultimate Question of Life, the Universe, and Everything".

   NB. After first iteration of sin or cos we are in [-1 ; 1], so any other real number can be chosen as a starting point in simple iteration.

   NB. Let's take 1 as a starting point this time.

   load 'trig'

   NB. Adverb Iter is defined using modifier trains.

   NB. u Iter is a verb which calculates for each atom of y a pair of boxes:

   NB. fixed point of u found by iteration from input starting point ; number of performed iterations.

   Iter =: ({: ; #)@(^:a:)"0

   NB. Let's begin with simpler example (cos instead of sin).

   NB. Root of f(x) = x - cos x.

   NB. Newton-Raphson method.

   NB. Quadratic convergence.

   (] - (] - cos) % 1 + sin) Iter 1

↌ↀↀ€â†€Ã¢â€ €Ã¢â€ €Ã¢â‚¬Ã¢â€ €Ã¢â€ €Ã¢â€ €Ã¢â€¬Ã¢â€ ¬â†€Ã¢â€

ↂ0.739085ↂ5ↆ‚

ↆↀↀ¬â†€Ã¢â€ €Ã¢â€ €Ã¢â‚¬Ã¢â€ €Ã¢â€ €Ã¢â€ €Ã¢â‚¬Ã¢â€ ´â†€Ã¢â€ ˜

   NB. Banach's method (simple iteration).

   NB. Linear convergence.

   cos Iter 1

↌ↀↀ€â†€Ã¢â€ €Ã¢â€ €Ã¢â‚¬Ã¢â€ €Ã¢â€ €Ã¢â€ €Ã¢â€¬Ã¢â€ ¬â†€Ã¢â€ €Ã¢â€ ↂ0.739085ↂ77ↆ‚

ↆↀↀ¬â†€Ã¢â€ €Ã¢â€ €Ã¢â‚¬Ã¢â€ €Ã¢â€ €Ã¢â€ €Ã¢â‚¬Ã¢â€ ´â†€Ã¢â€ €Ã¢â€ †˜

   NB. And go back to original case with sin.

   NB. Root of f(x) = x - sin x.

   NB. The root is 0, but the following result is a number close to 0 due to the floating-point arithmetic.

  

   NB. Newton-Raphson method.

   NB. Linear (not quadratic!) convergence, because f'(0) = 1 - cos 0 = 0.

   (] - (] - sin) % 1 - cos) Iter 1

↌ↀↀ€â†€Ã¢â€ €Ã¢â€ €Ã¢â‚¬Ã¢â€ €Ã¢â€ €Ã¢â€ €Ã¢â€¬Ã¢â€ €Ã¢â€ €Ã¢â€ ¬â††€â†€Ã¢â€

ↂ7.29388e_9ↂ45ↆ‚

ↆↀↀ¬â†€Ã¢â€ €Ã¢â€ €Ã¢â‚¬Ã¢â€ €Ã¢â€ €Ã¢â€ €Ã¢â‚¬Ã¢â€ €Ã¢â€ €Ã¢â€ ´â††€Ã¢â€ €Ã¢â€ ˜

r>

   NB. Simple iteration method.

   NB. The following has slow convergence, because sin x = x - x^3 / 3! + x^5 / 5! - ...

   NB. In other words lim (x -> 0) sin x / x = 1.

   NB. sin Iter 1

   NB. In the book Asymptotic methods in analysis by N. G. de Bruijn there is a proof that

   NB. x_n - x_{n+1} = 0.5 * sqrt(3) * n^(-3/2) + O(n^(-5/2) log n) where x_n is sin^:n x_0 in J notation and 0 < x_0 < PI.

   NB. x_0 is 1 in our case.

   NB. Let's compare the formula from the book with calculations:

   (%: ^&3 <: 1e6) %~ 0.5 * %: 3

8.66027e_10

   -/ _2&{. sin^:(< 1e6) 1

8.66014e_10

   NB. It may be interesting to check the number of iterations in above methods for double-doubles (use 11&c. in J9.6) or change comparison tolerance (9!:19).

Marcin

On Aug 2, 2024, at 5:21 PM, Martin Kreuzer <in...@airkreuzer.com> wrote:

Hi Marcin -

Thanks for the thorough explanation (regarding dyadic bonded verb).

About your two root finding examples:

I tried some finite numbers (on the left) to understand what they do,

and (with sin) experienced the slow convergence toward zero.

I have never come across a construct as  _ sin 42  before.

- Is that Newton-Raphson in disguise ?

- Any specific reason for argument 42 ?

-Martin

At 2024-08-01 08:15, you wrote:

This bite can lead to possibly infinite calculations when performing fixed-point iteration (I did it by mistake last week), for example:

  load 'trig'

   cos

2&o.

   _ cos 42 NB. linear convergence for all real numbers (solution of the equation cos x = x)

0.739085

   _ sin 42 NB. very slow convergence to 0 (solution of the equation sin x = x)

Convergence to 0 can be seen by for example:

   |. (< 1000) sin 42

This unintuitive trick in J led me to the above discoveries!

Marcin

On Aug 1, 2024, at 9:11 AM, Jan-Pieter Jacobs < janpiete...@gmail.com> wrote:

Hi Martin,

In the first tacit version of gftpr, (4&* + $:@<:) is a fork, called monadically, so 4&* is used as monad.

In the last version of gftpr, (4&+ $:@<:) is a *hook*, used monadically. This means 4&+ is called dyadically, which is equivalent to (4&+@])^:[ which happens to be equivalent to 4&* + ] .

e.g.:

   2 (4&+) 0

8

   (4&*+]) 5

25

   (4&+]) 5

25

   5 (4&+) 5

25

   5 (4&+@]^:[) 5

25

   +/5,5#4

25

Dyadic bonded verbs are a bit of an oddball in J that might bite you if you're not sure whether verbs are used monadically or dyadically in a sentence.

Hope this helps,

Jan-Pieter

On Thu, 1 Aug 2024, 08:28 Martin Kreuzer, <in...@airkreuzer.com> wrote:

Dear all -

As an exercise I wrote a simple verb which uses recursion:

gftpr=: monad define ("0)

 select. y

  case.  0 do. 0

  case.    do. (y*4) + gftpr y-1

 end.

)

This is what I came up with translating it to tacit:

gftpr=: 0:`(4&*+$:@<:)@.(1&<:)"0 M.

   gftpr i.10

0 4 12 24 40 60 84 112 144 180

By mere accident I found, that /this/ verb (having dropped Times (*))

gftpr=: 0:`(4&+$:@<:)@.(1&<:)"0 M.

gives me the /same/ result.

And this I do not understand.

   jver''

j9.6.0-beta14/j64avx2/windows/commercial/ www.jso