Newsgroup: it.comp.lang.visual-basic
Titolo: [SPAM] Algoritmo divisione

Ho trovato (non scoperto, l'ha ideato Newton) un algoritmo ottimo per
ricavare il reciproco di un numero ovvero 1/x.
E' iterativo e permette di sapere esattamentente quante cifre sono
corrette ad ogni iterazione.
Inoltre converge al risultato piuttosto velocemente se il valore iniziale
(da indovinare) è abbastanza vicino al risultato.
In pratica mi sono dovuto occupare solo di quest'ultimo aspetto, e mi sono
ritrovato con un algoritmo per le divisioni abbastanza veloce, visto che
A/B=A* 1/B
L'algoritmo, per chi fosse interessato è il seguente:
Sia N il numero di cui si vuole trovare il reciproco, si parte
inizializzando X ad un valore il più vicino possibile al risultato che si
vuole ottenere, poi si calcola continuamente la formula:
Xnuovo  =  Xvecchio  *  (2 - N * Xvecchio)
si cicla finche' |Xnuovo  - Xvecchio| < precisione desiderata.
Ad ogni iterazione si guadagnano sempre più cifre decimali, ma le
moltiplicazioni diventano sempre più lente.
Per questo sto cercando un nuovo metodo per le moltiplicazioni.
Per chi volesse provare il codice, trova il progetto completto di sorgenti
(sempre più illeggibili a causa della mia trascuratezza) qui:
http://www.unbelsito.com/vb/molt.0.4.zip
Ho aggiunto anche un paio di funzioni ovvie (fattoriale/esponenziale con
esponente intero) e altre per calcolare Pi greco e la radice quadrata di
un numero, ma sono poco accurate e lentissime.
Commento finale:
mi sto iniziando allo studio di CSharp di .NET; ho provato l'overloading
degli operatori: è fantastico e sarebbe proprio il metodo giusto per
gestire una classe di numeri personalizzata, pur mantenendo invariato il
codice chiamante (a parte le definizioni delle variabili).
termoPilucco
-- 
questo articolo e` stato inviato via web dal servizio gratuito 
http://www.newsland.it/news
 segnala gli abusi ad 
ab...@newsland.it

 
Bill Gates ed i suoia ccoliti un giorno sosterranno di aver inventato la 
  programmazione ad oggetti! :-(
Benvenuto fuori dal tunnel (di VB).
:-)
ciao
	maxx
-- 
NOSPAM: Rimuovere i trattini dallo username!
Cut hyphens from my username!

> mantenendo invariato il codice chiamante (a parte le definizioni
Dicesi ereditarietà...
chi qui dentro ha la fortuna/sfortuna di lavorare anche in C lo sa :-)
Anche io penso di cominciare a fare qcosa con C#...
vedo che è li che si sta puntando...
-- 
Alex {per email metti '[NOSPAM]' nell'oggetto}
"Un uomo saggio impara dall'esperienza,
un uomo ancora più saggio impara dall'esperienza degli altri." (Saggio
Cinese)

 ricavare il reciproco di un numero ovvero 1/x.
<cut>
Lo stesso autore ha anche trovato un'algoritmo per calcolare la radice
quadrata di un numero.
Devi iterare la formula [(n/a)+a]/2 dove n e' il numero da cui ricavare la
radice, a e' la radice da trovare.
Per velocizzare il calcolo si parte prendendo una a che abbia la meta delle
cifre che compongono il numero n.
Si continua a calcolare a ogni volta utilizzando quella ricavata
precedentemente fino a che si ricavano 2 valori che sono dentro la
tolleranza desiderata.
Oppure un'altro metodo per calcolare funzioni come radici, divisioni,
funzioni trigonometriche etc. e' quello di utilizzare il metodo CORDIC il
quale permette solamente con degli shift e somme/sottrazioni di calcolare
qualsiasi funzione.
A causa di queste sue caratteristiche il metodo viene utilizzato per
implementare i calcoli in 'Hardware' tipo sulle FPGA.
Ciao
Giuseppe

 chi qui dentro ha la fortuna/sfortuna di lavorare anche in C lo sa :-)
Non c'è in C, solo in C++ :)


implementare i calcoli in 'Hardware' tipo sulle FPGA.
Questo e' molto interessante :) 
cerchero' info... ma adesso ho trovato info circa un metodo per
velocizzare molto le mie moltiplicazioni e, magari, lo userň anche per le
somme.


E io che mi stavo rompendo la testa per cercare di ottimizzare la tua idea
sulle divisioni con resto negativo...
Cmq ora mi scarico il sorgente e vedo come gira.
bye
-- 
Esistono 10 tipi di persone: chi conosce il binario e chi no.
Gestione Ottica - Gestionale per Ottici e Programmi Gratuiti su:
http://www.nicolaottomano.it

Cmq ora mi scarico il sorgente e vedo come gira.
Adesso la divisione non gira male.
Però utilizza iterativamente la moltiplicazione, la quale rallenta non appena i
numeri diventano troppo grossi.
credo che la moltiplicazione computi qualcosa tipo n^2 passaggi (con n=numero
cifre dei moltiplicandi), come l'ordinamento di belzebù, insomma.
Ho trovato molto su come ottimizzare la moltiplicazione: un metodo promette di
eseguire n*log(n) passaggi, ma si basa sulle FFT che a loro volta si basano
sulla rappresentazione binaria dei numeri, ma la classe che uso si basa sulla
rappresentazione decimale, quindi la cosa è impraticabile a meno di costose
conversioni.
Tra parentesi, per un attimo ho pensato di passare alla rappresentazione in base
210 :) 
Infatti così facendo si possono rappresentare in modo semplice e finito frazioni
come 1/2, 1/3, 1/5 e 1/7 (infatti 210=2*3*5*7) e non mi devo partare sempre
appresso i relativi decimali periodici che occupano tutte le cifre di precisione
desiderate dal chiamante.
Comunque, tornando alle moltiplicazioni, un altro tizio ha risolto
ricorsivamente:
-siano a e b numeri troppo grandi per essere moltiplicati tramite long.
-a può essere visto come a1*10^n+a2  e b come b1*10^n+b2 (in soldoni si dividono
i due numeri grandi nella loro parte sinistra di n cifre e nella destra delle
rimanenti).
-quindi a*b=[fatti i calcoli]= tre moltiplicazioni di numeri di ordine dimezzato
rispetto agli originali.
-ricorsivamente si continua finchè i prodotti da eseguire stanno in un long e si
usa la moltiplicazione hardware.
Il bello è che l'ho implementato facilmente.
Il brutto è che, misteriosamente,  è di gran lunga più lento del metodo Belzebù.
Probabilmente è un problema della mia particolare implementazione (ogni tanto
penso di non usare più stringhe, ma array di byte, vista le lentezza delle
operazioni su stringhe).
Ah... ho trovato in giro anche un'ottima formula per e^x (un'ottimizzazione di
Taylor) con la quale di ricava facilmente a^x.
Alla fine, se riuscirò ad ottenere velocità decenti, potrò implementare la
funzione "vàluta" che, data un'espressione formata dagli operatori implementati
e il grado di precisione desiderato, ne calcola il valore.
Poi magari darò una ripulita al codice, 'che sembra ci siano passati gli
alieni...
termoPilucco

 gli alieni...
O Belzebù.... :-P


O Belzebů.... :-P
Eggiŕ, c'č anche il suo zampino lě dentro :)
termoPilucco