Centro del quadrato

Autore: 1949 – John von Neumann
Wikipedia: Middle-square method

Prova…

Seme
Cifre (n)
Quanti?

Moneta di Buffon

L’esperimento consiste nel lanciare una moneta su di un pavimento coperto da mattonelle quadrate.
La probabilità che la moneta tocchi il bordo di una mattonella dipende dalla dimensione (raggio) della moneta.

Per semplificare

  1. Il lato della piastrella, bb_html_m7a2ee505
  2. La superficie della piastrella, bb_html_m3d2d581b
  3. Il raggio della moneta, bb_html_m519aa403

monete3La moneta non tocca il bordo se il suo centro cade a una distanza dai bordi maggiore del suo raggio, cioè se cade all’interno di un quadrato interno con

  1. Lato interno,  bb_html_b4f807b
  2. Superficie del quadrato interno,  bb_html_a206ff9

La probabilità che la moneta cada all’interno è data dal rapporto tra la superficie del quadrato interno e della piastrella

bb_html_m63281f2f

La probabilità di toccare il bordo

 bb_html_296e9817

Teoricamente, la probabilità che la moneta tocchi il bordo della piastrella nei 3 casi in figura è

R 1/8 2/8 3/8
LI 6/8 4/8 2/8
SI 36/64 16/64 4/64
P 28/64 = 0,4375 48/64 = 0,75 60/64 = 0,9375

Naturalmente

  • Se R –> 0 allora P –> 0
  • Se R –> 1/2 allora P –> 1

Metodo Monte Carlo

Il fenomeno viene simulato con le seguenti ipotesi

  • il centro della mattonella è (0,0)
  • le coordinate casuali del centro della moneta sono (x,y)
  • bb_html_m437a8737
  • la moneta tocca il bordo di una mattonella sebb_html_e34aac9 oppure bb_html_3eb68f7

Simuliamo N lanci, contando le occorrenze in cui la moneta tocca il bordo della mattonella e confrontiamo le frequenze relative con le probabilità teoriche

R 1/8 2/8 3/8
? ? ? N=10
? ? ? N=100
? ? ? N=1000
? ? ? N=10000
P 0,4375 0,75 0,9375

Metodo babilonese

L’algoritmo è noto come metodo babilonese oppure di Archita, di Erone, …

Con n_4

  • Sia n il numero in ingresso e x la sua radice quadrata allorax_n
  • Sia xa una prima approssimazione della radice quadrata di n allora x_xa_n
  • Anche xb è un’approssimazione e inoltre (in questo primo passo…) xb_x_xa_n
  • Sia xm, la media di xa_ e xb_ allora xb_xm_xa
  • Ricomincia utilizzando per xa_ la media appena calcolata xm_

Esempio

Sia n=256

xa_ xb xm
128 2 65
65 3,93846 34,46923
34,46923 7,42691 20,94807
20,94807 15,43620 16,01029
16,01029 15.98971 16,00000

babylon2Osserva il grafico

  • xa_ e xb_ convergono verso x
  • xm_ è sempre in mezzo…

A ogni iterazione

  • xa_ si allontana da n e si avvicina da destra a x
  • xb_ si allontana da 2 e si avvicina da sinistra a x
  • xm_ si trova tra xb_ e xa_
  • xb_x_xm_xa_n

babylon3


In realtà l’algoritmo funziona anche se n_0 e se xa_0

A ogni passo

  • se xa_x allora xb__x
  • se xa__x allora xb_x
  • xm_ sarà compreso tra xa_ e xb_ e sempre più vicino a x

Nei primi passi xa_ e xb_ potrebbero scambiarsi di posto ma poi tutto continuerà come prima.


Per decidere quando fermare l’iterazione si può calcolare

  • e_a, errore assoluto
  • e_r, errore relativo, errore in rapporto all’ultima approssimazione

e stabilire un valore soglia al di sotto del quale l’iterazione si arresta.


RISORSE

Numeri pseudocasuali – Funzioni

Gli ambienti di sviluppo rendono disponibili una o più funzioni per la generazione di numeri casuali

Reali Interi
BASIC RND() [0.0…1.0)
Calc
Excel
CASUALE.TRA(INF; SUP) [INF, SUP]
CASUALE() [0.0…1.0)
GeoGebra random() [0.0…1.0)
Java
Javascript
Math.random() [0.0…1.0)
Pascal Random(SUP) [0, SUP-1]
Random [0.0…1.0)
Python random.randint(INF,SUP) [INF, SUP]
random.random() [0.0…1.0)

Numeri in un intervallo

A partire dalle funzioni disponibili si possono ottenere numeri distribuiti uniformemente in un intervallo a piacere

Reali

[0..SUP) [INF..SUP)
tutti SUP*FUNZIONE() (SUP-INF)*FUNZIONE()+INF

Interi

[0, SUP-1] [1, SUP] [INF, SUP]
Java (int)(SUP*Math.random())
(int)(SUP*Math.random()+1) (int)((SUP-INF+1)*Math.random()+INF)
Javascript Math.floor(SUP*Math.random())
Math.floor(SUP*Math.random()+1) Math.floor((SUP-INF+1)*Math.random()+INF)
Pascal Random(SUP) Random(SUP)+1 Random(SUP-INF+1)+INF

Prova!

Reali Interi
Math.random() [0..1[ Con Math.floor(...)
SUP*Math.random()
SUP*Math.random()+1
(SUP-INF)*Math.random()+INF
(SUP-INF+1)*Math.random()+INF
INF SUP

LCG

Linear Congruential Generator

lcg

a
c
m
seme
n