Discussion :

[Jedai]

De toute façon, ce forum est un peu universel...
(***) et (&&&) sont des opérateurs que j'ai emprunté à Control.Arrow, ils s'appliquent à toutes les instances de la typeclass Arrow, y compris donc aux fonctions (consulte cette page et les liens afférents éventuellement pour plus de détail sur Arrow).

En gros ils sont déjà très utiles même si on ne programme pas avec des Arrow, leurs instances sur les fonctions sont :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
(a -> b) -> (c -> d) -> (a, c) -> (b, d)
f *** g (x,y) = (f x, g y)
 
(a -> b) -> (a -> c) -> a -> (b, c)
f &&& g x = (f x, g x)

Mon "dup f" est donc juste une fonction qui applique f aux deux composantes d'un tuple.

Les &&& et les *** quand on y est habitué rendent évident le flot de l'évaluation, mais on aurait aussi pu écrire :

Code Haskell :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
pairs = zipWith (\p2n sn->(p2n * abs (re sn), p2n * abs (im sn))) p2 s
    where
      s = iterate (<*> (3 :+ 4)) (1 :+ 0)
      p2 = iterate (* 2) 1

(mais ça fait trop de parenthèses et de redondances à mon goût)

--
Jedaï

[Nemerle]

Merci Jedai, maintenant c'est clair!

[pseudocode]

Notez que nos méthodes ne sont pas très adaptées au calcul d'un TP en particulier, elles pourraient faire beaucoup mieux avec une simple exponentiation rapide.

On a quand meme bien optimisé le calcul depuis le post #2...


Pour faire plaisir a Jediai, la version avec exponentiation rapide:

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
 
import java.math.BigInteger;
 
class DVPThread433050 {
 
	// internal class for handling big complex numbers
	class BigComplex {
		private BigInteger real,imag;
		public BigComplex(int r,int i) {
			this.real=BigInteger.valueOf(r);
			this.imag=BigInteger.valueOf(i);
		}
		public void multiply(BigComplex c) {
			BigInteger newreal=real.multiply(c.real).subtract(imag.multiply(c.imag));
			BigInteger newimag=real.multiply(c.imag).add(imag.multiply(c.real));
			this.real=newreal;
			this.imag=newimag;
		}
	}
 
	// compute triplet at rank n
	public BigInteger[] computeTP(int n) {
		// with cos(t)=3/5, sin(t)=4/5 compute X
		// X = 10^n.(cos(nt)+i.sin(nt))
		//   = 10^n.(cos(t)+i.sin(t))^n
		//   = 10^n.5^(-n).(3+i.4)^n
		//   = 2^n.(3+i.4)^n
 
		// compute (3+i.4)^n (by repeated squaring)
		BigComplex X = new BigComplex(1,0);
		BigComplex EXP = new BigComplex(3,4);
		for(int p=n;p!=0;p=p>>1,EXP.multiply(EXP)) {
			if ((p & 1)!=0) X.multiply(EXP);
		}
 
		// multiply by 2^n
		BigInteger POW2=BigInteger.valueOf(2).pow(n);
		BigInteger a = X.real.multiply(POW2);
		BigInteger b = X.imag.multiply(POW2);
 
		// return TP
		BigInteger POW10=BigInteger.valueOf(10).pow(n);
		return new BigInteger[] {a.abs(),b.abs(),POW10};
	}
 
	public static void main(String[] args) {
		int rank = 10000;
		long l0 = System.currentTimeMillis();
		BigInteger[] tp = new DVPThread433050().computeTP(rank);
		long l1 = System.currentTimeMillis();
		System.out.println("TP("+rank+")=(\n"+tp[0]+"\n"+tp[1]+"\n"+tp[2]+")");
		System.out.println("duration: "+(l1-l0)+"ms");
	}
}

TP(100) en 0 ms
TP(1000) en 15 ms
TP(10000) en 78 ms
TP(100000) en 4900 ms

[Nemerle]

et bien! au moins, mon problème vous aura passionné...

[Nemerle]

ultime add-on: un ancien collègue prof en spé à trouvé cet énoncé avec solution dans un bouquin de math teuton de 1973...

[pseudocode]

ultime add-on: un ancien collègue prof en spé à trouvé cet énoncé avec solution dans un bouquin de math teuton de 1973...

et c'est quoi leur solution a eux ?

[Nemerle]

bein la notre, en démontrant l'unicité avec des théorèmes de math à la c.....

[pseudocode]

bein la notre, en démontrant l'unicité avec des théorèmes de math à la c.....

Whouaa... j'ai trouvé la solution d'un exo de 1973. Je suis pas peu fier

[raphil]

bonjour à tous,

j' ai lu vos posts et on peut simplifier un peu en reprenant l'idée de pseudocode.
En effet posons cos(t)=3/sqrt(10) et sin(t)=1/sqrt(3).
on a par récurrence :
cos(nt) = u(n)/(sqrt(10))^n
cos(nt) = v(n)/(sqrt(10))^n
où u(n) et v(n) sont des entiers relatifs.
Par exemple u(1) = 3 et v(1) = 1.
Puis avec les formules de trigo, on obtient par exemple :
u(n+1) = 3 u(n) - v(n)
v(n+1) = 3 v(n) + u(n)

u(2n) = u(n)^2 - v(n)^2
v(2n) = 2 u(n) v(n)

u(n+m) = u(n) u(m) - v(n) v(m)
v(n+m) = v(n) u(m) + u(n) v(m)

En fait on remarque que si on pose x(n) = u(n) + i v(n)
avec i^2 = -1
on a :
x(n+1) = x(n) x(1)
x(2n) = x(n)^2
x(n+m) = x(n) x(m)
C'est logique d'après les formules de de Moivre!
Cela permet de calculer les u(n) et v(n) pour n>1 comme

u(2) = 8
v(2) = 6

u(3) = 18
v(3) = 26
...

Et on peut écrire un programme avec exponentiation rapide.
J' ai utilisé la librairie gmp pour les calculs sur grands entiers.

Cordialement,
raphil

[Jedai]

raphil, tout ce que tu dis était déjà dans les propositions de Pseudocode, c'est ce qui a été implémenté dans tous les derniers codes, tu peux même voir que j'ai proposé l'exponentiation rapide dans mon dernier post (mais ça ne correspondait pas à la demande initiale qui était une liste de toute les puissances jusqu'à un certain point) et que Pseudocode l'a implémenté dans son dernier code. Et bien sûr nous avons tous utilisé des entiers en précision arbitraire (mon code Haskell utilise d'ailleurs GMP indirectement, je crois).

--
Jedaï

[c-candide]

B'jour,

tout est presque dans le titre: en se fixant un nombre de décimales n, il n'existe qu'un couple de solution de x^2+y^2=1 (à échange près).

Par exemple,
pour n=1, 0.6 et 0.8 sont les seules solutions de x^2+y^2=1
pour n=2, 0.28 et 0.96 sont les seules solutions de x^2+y^2=1
...

Quelqu'un connait un méthode pour le démontrer, ou un algo pour trouver la solution à l'ordre n ??

Voici une idée de démonstration qui a l'avantage d'être constructive et que j'illustre par un exemple. Il faut connaître
des rudiments sur l'anneau des entiers de Gauss (c'est le sous-anneau du corps des nombres
complexes formés des a+ib, avec a et b entiers et comme d'habitude i*i=-1), en particulier
que cet anneau est factoriel, voir un cours d'algèbre pure de L3-M1.

Soit par exemple à trouver les solutions de l'équation qui sont les décimaux contenant exactement n=4 vraies décimales.
On se ramène donc à résoudre dans N l'équation suivante : a^2+b^2=10^8 (les solutions
initiales étant alors x=a/10000 et y=b/10000).

L'idée (classique) est alors de se placer dans l'anneau G des entiers de Gauss. On sait que c'est un anneau factoriel.

On a les décompositions suivantes en produit d'irréductibles (facile) :
2=(1-i)(1+i) et 5=(2+i)(2-i)

donc on obtient
a^2+b^2=(a+ib)(a-ib)=(1-i)^8*(1+i)^8* (2+i)^8*(2-i)^8

et c'est là qu'intervient l'argument-clé : par factorialité, on a, à un inversible près (les inversibles de G ont juste pour rôle ici d'échanger a et b ou de les changer en leur opposé),

a+ib=(1+i)^8*(2+i)^k*(2-i)^(8-k) pour un certain k parmi 0,...,8 (j'ai omis un détail).

Si on ne prend pas k=8 on va faire apparaître un puissance de 10 si bien qu'on n'aura pas les 4 décimales vraies. D'où a+ib=(1+i)^8*(2+i)^8 et le calcul donne a+ib=(1+i)^8*(2+i)^8 =-8432-5376*I.

Traduction :

l'unique couple avec 4 vraies décimales est (au signe et à échange près) :
x=0.8432 et y = 0.5376.

En espérant ne pas avoir dit de bêtise.

EDIT
Légère précision, orthographe