Newsgroup: it.comp.lang.c
Titolo: Come fa un elaboratore per calcolare un seno, un coseno o una radice quadrata?

Voglio applicare le funzioni seno, coseno e radice quadrata agli interi,
ovvero
int sen(int x);
int cos(int x);
int sqrt(int x);
naturalmente con una certa approssimazione, senza apportare alcun tipo di
cast;
come fanno i calcolatori per risolvere queste funzioni?
Io avevo pensato a Taylor, ma non sono sicuro, qualcuno mi aiuta?

Io avevo pensato a Taylor, ma non sono sicuro, qualcuno mi aiuta?
Esattamente: fanno lo sviluppo in serie di Taylor, fermandosi ad un certo
ordine.

 Io avevo pensato a Taylor, ma non sono sicuro, qualcuno mi aiuta?
No, Taylor non va bene in quanto la convergenza di questa serie e' in
genere buona solo in un intorno 'piccolo' del punto iniziale e ti
ritroveresti costretto ad usare un numero enorme di derivate appena ti
allontani un po' dal punto iniziale.
Seno e Coseno vengono in genere ridotti al primo quadrante (pi/2) o
addirittura ottante (pi/4) e poi calcolati con una serie , tieni conto
che in genere si usa un algoritmo che da contemporaneamente seno e
coseno in un colpo solo ( tutti i ragionamenti sono in radianti)
quindi per le funzioni trigonometriche basterebbe una tabellina di 45
punti.
Maggiori informazioni le puoi avere cercando per 'Netlib' o per
'Numerical Recipes'
il primo e' un archivio di programmi di tipo numerico e il secondo e' un
libro con sorgenti sempre sullo stesso argomento
Marco Colandrea

 Io avevo pensato a Taylor, ma non sono sicuro, qualcuno mi aiuta?
Si, mi sembra che normalmente vengano utilizzati degli sviluppi in
serie. Nel tuo caso, trattando solo numeri interi, potresti utilizzare
delle tabelle precalcolate, se vuoi qualcosa di più veloce. Il C++
permette di costruirne a tempo di compilazione attraverso la
meta-programmazione template. Questo significa migliore possibilità di
manutenzione e modifica delle stesse.
EMG

Per il seno etc. non saprei; comunque su Numerical Recipes (che altri
ti hanno indicato) ci sono tutte le basi.
Per la radice quadrata intera ho io questa chicca che ti passo; la
procedura e' puro C, non C++.
-- 
Maurizio Loreti                      
http://wwwcdf.pd.infn.it/~loreti/mlo.html
Un. of Padova, Dept. of Physics - Padova, Italy          
lor...@padova.infn.it
----------------------Begin included file: usqrt.c
#include <string.h>
#define BITSPERLONG 32
#define TOP2BITS(x) ((x & (3 << (BITSPERLONG-2))) >> (BITSPERLONG-2))
/* usqrt:
    ENTRY x: unsigned long
    EXIT  returns floor(sqrt(x) * pow(2, BITSPERLONG/2))
    Since the square root never uses more than half the bits
    of the input, we use the other half of the bits to contain
    extra bits of precision after the binary point.
    EXAMPLE
        suppose BITSPERLONG = 32
        then    usqrt(144) = 786432 = 12 * 65536
                usqrt(32) = 370727 = 5.66 * 65536
    NOTES
        (1) change BITSPERLONG to BITSPERLONG/2 if you do not want
            the answer scaled.  Indeed, if you want n bits of
            precision after the binary point, use BITSPERLONG/2+n.
            The code assumes that BITSPERLONG is even.
        (2) This is really better off being written in assembly.
            The line marked below is really a "arithmetic shift left"
            on the double-long value with r in the upper half
            and x in the lower half.  This operation is typically
            expressible in only one or two assembly instructions.
        (3) Unrolling this loop is probably not a bad idea.
    ALGORITHM
        The calculations are the base-two analogue of the square
        root algorithm we all learned in grammar school.  Since we're
        in base 2, there is only one nontrivial trial multiplier.
        Notice that absolutely no multiplications or divisions are performed.
        This means it'll be fast on a wide range of processors.
*/
struct int_sqrt {
	unsigned sqrt,
		 frac;
};
void usqrt(unsigned long x, struct int_sqrt *q)
{
	unsigned long a = 0L;			/* accumulator */
	unsigned long r = 0L;                   /* remainder */
	unsigned long e = 0L;                   /* trial product */
	int i;
	for (i = 0; i < BITSPERLONG; i++)	/* NOTE 1 */
	{
		r = (r << 2) + TOP2BITS(x); x <<= 2; /* NOTE 2 */
		a <<= 1;
		e = (a << 1) + 1;
		if (r >= e)
		{
			r -= e;
			a++;
		}
	}
	memcpy(q, &a, sizeof(long));
}
#ifdef TEST
#include <stdio.h>
#include <stdlib.h>
main(void)
{
	int i;
	unsigned long l = 0x3fed0169;
	struct int_sqrt q;
	for (i = 0; i < 101; ++i)
	{
		usqrt(i, &q);
		printf("sqrt(%3d) = %2d, remainder = %2d\n",
			i, q.sqrt, q. frac);
	}
	usqrt(l, &q);
	printf("\nsqrt(%lX) = %X, remainder = %X\n", l, q.sqrt, q.frac);
      return 0;
}
#endif /* TEST */

 cast;
Scusami ma che senso ha ritornare un intero delle funzioni seno e coseno il
cui itervallo é compreso tra -1 e 1 e gli unci iteri ivi compresi sono
appunto -1,  0 e 1  ???
Ciao.

int sqrt(int x);
Be', ma il risultato *intero* di un seno che utilita' ha ?
Voglio dire, il seno di un angolo e' un valore sempre compreso tra -1
e 1.
Quindi i valori interi assumibili da sin(x) per x in [0,360[ sarebbero
-1, 0 e 1.
Ti interessano solo questi valori ?
In questo caso puoi costruire una tabella precalcolata sfruttando la
funzione seno del calcolatore, cioe' qualcosa del tipo :
static int tavola_seno[360] ;
...
for (alfa = 0 ; alfa < 360 ; alfa++)
    tavola_seno[alfa] = (int)sin(alfa*3.1415927/180) ;
Per quanto riguarda la routine di radice quadrata puoi utilizzare
l'algoritmo di approssimazione di Newton delle suddivisioni
successive.
Magari con un margine di tolleranza...

 appunto -1,  0 e 1  ???
Uhm, domanda interessante. Non ci avevo pensato. Sono curioso di sapere
cosa risponde l'amico...
EMG

Ciao.
-----------------------------------------------------------
Christian Salvaneschi
Casarza Ligure, Genova, Italy
e.mail: 
crj...@geocities.com
 (remove 214 for email reply)
web: 
http://www.geocities.com/SiliconValley/Lakes/5139

ancora meno senso....
Non e' vero.
Il dominio della funzione seno e' tutto l'insieme dei numeri reali, i
quali comprendono *anche* i numeri interi.
E' poi si puo' calcolare il seno anche di 4560 radianti.
A prescindere dal fatto che l'argomento sia espresso in radianti o
meno, calcolare il seno di un numero intero ha senso.
E poi non e' detto che anche ottenerne un risultato intero non abbia
senso (d'altronde non si puo' affermare che la funzione sia costante).
Infatti, a rigor di logica, la funzione seno assume infinite volte il
valore 0 ma anche infinite volte il valore 1 ed anche infinite volte
il valore -1.
Bisogna solo vedere che tipo di applicazione si sta sviluppando e a
cosa possano servire questi unici tre valori.
E' discutibile l'utilita', ma non il senso di una funzione del genere.

E' discutibile l'utilita', ma non il senso di una funzione del genere.
Quello intendevo, ha poco senso  a livello applicativo...
Visto che inoltre l'eventuale implementazione per numeri interi non è
che possa differire a livello di prestazioni dall'implementazione per
numeri reali....


>


 numeri reali....
Invece differisce e come! Es.:
int intsin( int angle )
{
    if ( angle == 90 )
        return 1;
    if ( angle == 270 )
        return -1;
    return 0;
}
o analogamente se si vuole arrotondare all'intero piů vicino.
EMG

 Se ho capito bene, come si fa a precalcolare 2^32 numeri?
Scusa, ma avevi detto che volevi delle funzioni che lavorassero sugli
interi, giusto? Allora, almeno per quanto riguarda le funzioni
trigonometriche, non basta precalcolare 360 numeri?
EMG

numeri reali....
A cosa possa servire una funzione del genere non lo so, ma ad esempio
una prima cosa che mi viene in mente e' che potrebbe mantenere una
condizione di "false" per un certo tempo e ad intervalli regolari far
comparire un "true".
In quanto all'implementazione per numeri interi certo che differisce
da quella dei reali.
Una prima banale differenza e' quella che l'insieme dei numeri
naturali e' numerabile e quindi essi possono essere usati in C come
indici degli array.
Questo fornisce la base per una tabella precalcolata.

}
Se poi ci mettiamo un angle %= 360 all'inizio mi sembra perfetta ;)

trigonometriche, non basta precalcolare 360 numeri?
Esatto, addirittura ne basterebbe precalcolare 45 ed ottenere gli
altri come riferimenti all'origine degli assi cartesiani.

Non è questa la soluzione migliore...
provare per credere...

}
In effetti considerando l'argomento in gradi e non in radianti c'è
molta  differenza. Io ragionavo con l'argomento in radianti, e in quel
caso non c'è altra via....
