réponse
a1*a2 est 172 204 * 284 160;
b1b2 est 370 251 * 293 042;
(a1+b1)*(b1+b2) est 542
455 * 577 202.
premier sous-problème: 172 204 * 284 160;
les trois sous-sous-problèmes sont: 172*204 (48848),
204*160 (32640) et
376*444 (166944).
on soustrait les deux premiers du troisième: 85456 et
on fait l'addition
48 848 000 000
32 640
85 456 000
--------------
48 933 488 640
deuxième sous-problème: 370 251 * 293 042;
370*293 = 108410
251*042 = 10542
621*335 = 208035
soustraction: 208035-108410-10542=89083
108 410 000 000
10 542
89 083 000
--------------
108 499 093 542
troisième sous-problème: 542 455 * 577 202;
542*577 = 312734
455*202 = 91910
997*779 = 7776663
soustraction: 7776663- 312734-91910 = 372019
312 734 000 000
91 910
372 019 000
--------------
313 106 110 910
Retour au problème de départ: (a1+b1)*(a2+b2)-(a1b1+a2b2)
313 106 110 910
157 432 582 182
---------------
155 673 528 728
et l'addition finale:
48 933 488 640 000 000 000 000
108 499 093 542
155 673 528 728 000 000
------------------------------
48 933 644 313 637 227 093 542
L'algorithme minmax utilise 3n/2-2 comparaisons pour trouver le minimum et maximum de n nombres (n pair).
On considère la taille maximum de la pile utilisée
par
le tri rapide.
(on suppose que tous les éléments sont distincts)