Diviser par 10 en binaire ?

Sat Aug 18, 2007 4:38 pm   

Bonjour à tous,

La question va peut-être vous paraitre con, mais comment fait-on pour
diviser un chiffre par 10 en binaire (uniquement avec des operations
"logiques" quoi) ? et d'une manière générale, comment on fait pour diviser
ou multiplier un nombre dont le denominateur n'est pas une puissance de 2 ?
Je me suis un peu creusé la tête ce matin sans parvenir à en découvrir la
logique par moi même...

Si vous avez un liens qui traite de la vulgarisation de ce problème ça
serait sympa !

merci d'avance...

Sat Aug 18, 2007 6:08 pm   

Faire X = X - 10 et tester si X >0

répeter jusqu'à ce que X <= 0

le nombre de fois que vous aurez répété
donnera le resultat

Bon, c'est simple mais pas pas le plus rapide..............

"Adrien Gaudel" <adriennospaam_at_stable-boy.net> a écrit dans le message de
news: 46c7205f$0$25913$ba4acef3_at_news.orange.fr...

Sat Aug 18, 2007 6:54 pm   

"Adrien Gaudel" <adriennospaam_at_stable-boy.net> a écrit dans le message de
news: 46c7205f$0$25913$ba4acef3_at_news.orange.fr...

(par 10) seulement : Le plus simple est de soustraire le diviseur en
comptant le nombre
d'opérations
50/10:
50-10 = 40 :1 fois
40-10= 30 :2 fois
30-10= 20 :3 fois
20-10= 10 :4 fois
10-10= 0 :5 fois
Soit "5" (reste zéro )
Bonne soirée

Sat Aug 18, 2007 9:01 pm   

Adrien Gaudel wrote:

On peut diviser par une constante en multipliant par son inverse:
Par exemple x/10 = (x * 65536/10) >> 16
(Ajouter autant de bits que nécessaire pour obtenir un résultat
exact sur la plage de valeurs de x souhaitée).

On multiplie par une constante avec des additions et des décalages.
Par exemple x*10 = x*2 + x*8 = (x<<1) + (x<<3)

AC

Sat Aug 18, 2007 9:17 pm   

en ce 18/08/2007 18:38, Adrien Gaudel nous disait:

Il me semble que l'algorithme classique qu'on apprend à l'école primaire
se réduit à des opérations de logique simple en binaire, et ceci quel
que soit le diviseur.
La maîtresse elle disait de prendre le diviseur (de n chiffres) et de
chercher combien de fois il "tient" dans les n premiers chiffres du
dividende, ou n+1 si ça tient pas.
Le "combien de fois" en binaire, c'est 0 ou 1, c'est donc une simple
comparaison.
Ensuite, on calcule le reste intermédiaire (une simple soustraction), on
le complète à droite en "descendant" le chiffre suivant du dividende, et
ainsi de suite.
On peut imaginer d'optimiser un peu en vérifiant à chaque descente d'un
zéro que derrière, il n'y a pas que des zéros à la suite, pareil qu'en
base dix, ou n'importe quelle base d'ailleurs.

" There are only 10 types of people in the world: Those who understand
binary, and those who don't " ;-)

JLM

Sat Aug 18, 2007 9:19 pm   

"Adrien Gaudel" <adriennospaam_at_stable-boy.net> a écrit dans le message de
news: 46c7205f$0$25913$ba4acef3_at_news.orange.fr...

Mettre le nombre dans le registre N
Mettre le diviseur dix (1010) dans le registre D
Mettre un (1) dans le registre V
Mettre zéro (0) dans le quotient : registre Q
Boucle1 :
Décaler D et V de 1 bit à gauche (multiplication par deux)
Si D < N aller en Boucle1
Boucle2 :
Décaler D et V de 1 bit à droite (division par deux)
Si V = 0 c'est fini
Si D < N
Alors soustraire D de N, et ajouter V à Q
Aller en Boucle2

Voilà voilà

Sat Aug 18, 2007 10:08 pm   

Il faudrait que tu décrive ton Monde.

Dans un OS, tu laisse le compolateur se débrouiller.

En C, avec des flots, tu t'en fous.

Qaund tu travailles au bit près, ca va encore dépendre du contexte,
selon que tu es en assembleur, et selon le jeu d'instruction. Une
division par #10d est triviale sur un CISC (1 instruction, 2 cycles), et
va te prendre une bonne trentaine si tu la fais sut RISC avec une boucle
de durée déterminée (détesministe), tandis que sur RISC, la méthode la
plus simple à coder (soustractions consécutives) peut prendre quelques
cycles à plusieur milliers (si le nombre est grand).

Il faut décrire ou tu travaille, la largeur moyenne de la données
manipulée, la largeur du bus disponible (si tu espère au moins 4 lignes
dispo à gauche, la méthode de DF est facilement implémentable, et sera
détermministe niveau temps).

Si tu es en logique brutte (genre, circuits logiques série 4000 & 74LS )
tu trouvera des dessins basés sur des JKs qui font cela (pas très loin
des compteurs BCD, des drivers d'afficheurs 7 segments ...)

Il y a 30 ans, dans Ariane.1, on se prenais pas la tête avec le binaire;
on fesais tout en analogique, à coups d'AOs bien placés, et ca restait
quand même plus ou moins programmable.

La méthode de A.Caspis nécessite de disposer de flotants.

=> dépend du contexte.

--


"So all that's left, Is the proof that love's not only blind but deaf."
(FAKE TALES OF SAN FRANCISCO, Arctic Monkeys)

Sun Aug 19, 2007 1:19 pm   

"DEMAINE Benoit-Pierre" <nntp_pipex_at_demaine.info> a écrit dans le message de
news: 46c76df9$0$413$426a74cc_at_news.free.fr...

Euh non en fait j'étais carrement partis sur des portes logiques "à
l'ancienne" et je me demandais comment c'était possible de faire cette
operation en dehors de tout contexte "logiciel" (sans ALU, boucles, saut,
etc...) mais j'ai peur que dans ce cas la solution ne soit pas aussi simple
que ce que je ne l'esperais au départ...

Bien qu'en fait le problème de départ justement soit un peu plus simple :
diviser la frequence d'un signal (carré) par n (avec ici n=10) : mais là je
suis arrivé à la conculsion que le plus simple est d'utiliser un compteur
que l'on remet à 0 lorsqu'il arrive à la valeur n (en tout cas je ne dois
pas être loin de la meilleur solution possible pour ce problème)

Sun Aug 19, 2007 8:37 pm   

DEMAINE Benoit-Pierre wrote:

Ca marche aussi avec des entiers, à condition de s'assurer que
l'on reste dans la plage de validité de la formule.

(x*6554)>>16 donne exactement x/10 pour x compris entre 0 et 16388.

AC

Sun Aug 19, 2007 8:42 pm   

A. Caspis wrote:

Si les entiers sont sur 32 bits, oui. Sinon...

Nicolas

Sun Aug 19, 2007 11:01 pm   

C'est ce que je pensais aussi, mais, tout le monde est parti dans une
solution programmable.

Pour une division hard, j'ai évoqué les montages JK.

http://rabbit.eng.miami.edu/info/datasheets/
74LS56P 3x Frequency divider, 5:1, 5:1, 10:1
74LS57P 3x Frequency divider, 5:1, 6:1, 10:1

http://www.samengstrom.com/nxl/3246/cmos_index_page.en.html
4017 Decade counter/divider plus 10 decoded decimal outputs
4510 Presettable 4-bit BCD up/down counter

la théorie de ce que tu cherches:
http://en.allexperts.com/q/Electrical-Engineering-1356/flip-flops.htm
http://www.freshpatents.com/Circuits-and-methods-for-high-speed-and-low-power-data-serialization-dt20070719ptan20070168589.php

La pratique:
http://www.play-hookey.com/digital/frequency_dividers.html
http://www.doc.ic.ac.uk/~nd/surprise_96/journal/vol3/cwl3/test.html
(réponse A8)

utilisation d'un 4017 (évoqué plus haut)
http://www.engineering.wright.edu/~egr190/timeff/timeff.htm

oui il faut en fait faire une recheche coté "diviseur de fréquence", car
de nos jours, on fait ce genre d'opération en soft; on ne le fait en
hard que quand le soft est trop lent, cas qui n'arrive que pour ce qui
tourne plus vite que le coeur de calcul: son horloge !

--


"So all that's left, Is the proof that love's not only blind but deaf."
(FAKE TALES OF SAN FRANCISCO, Arctic Monkeys)

Sun Aug 19, 2007 11:14 pm   

Adrien Gaudel wrote:

sisi ca se cable avec des portes série 4000.


tu aurais dit dès le début que tu veux diviser une horloge ...

le 4017 ressemble à un calculateur hard.

De toute facon, avant d'avoir des PICs, tu crois qu'ils fesaient comment
les calculettes à pile y a 30 ans ? à coups de JKs !!!

Sauf que de nos jours, JK ou uC, le cout de la mise en boitier est
presque le même, et le cout du silicium est parafois comparable, donc le
composant le moins cher, sera le plus fabriqué par l'usine; voila
pourquoi une solution programmable est désormais "plus flexible *ET*
moins chère" d'une full custom, pour les produits <<simples>>.

un diviseur de fréquence se fait TOUJOURS à coups de flip-flops.

une division par 10 avec des flip flop, c'est un cas d'école quand tu
débute l'electronique logique.

*** *** ***

Tu as posé ta question de division binaire sans aucun contexte; il est
normal que ce soit parti dans tous les sens; tu n'a pas dit ni ce que tu
voulais diviser, ni le domaine ...

Techniquement, le sens premier de "division", consiste à trouver le
quotient; et numériquement, le plus simple est de le faire par calcul;
sauf que dans ton cas, tu veux diviser des évènements ... donc du temps,
et là, on ne s'intéresse pas au "quotien final", je dirais même qu'on
s'en fout C'est en fait le temps que tu multiplie ... puisque d'une
succession d'évènements courts, tu veux des évènements plus longs ...

voilà pourquoi, ce que tu veux, ce n'est pas diviser une fréquence, mais
multiplier un temps.

Une fois la question posée dans ce sens là, l'usage de portes 4000
devient évident ...

la fréquence est une notion abstraite; ca te parle à toi, mais pas aux
électrons; les electrons, ils comprennent la notion de temps, et dans la
dimension temps, tu fais une multiplication !!!

***

VRAIMENT à l'ancienne, tout se fesait avec des JKs.

--


"So all that's left, Is the proof that love's not only blind but deaf."
(FAKE TALES OF SAN FRANCISCO, Arctic Monkeys)

Mon Aug 20, 2007 1:02 pm   

Salut Adrien,
Tu t'es peut-etre creusé les meninges, mais tu n'as pas trop regardé google
quand meme.
Il y a une palanquée de CI diviseur par dix aussi bien en TTL qu'en CMOS:
tous les anciens frequencemetres a affichage digital des années 80 sont
basés sur des 7490 ou derivés. C'est un diviseur par 2 et par 5 cascadable,
on trouve meme le 74390 qui contient deux diviseurs par 5 et deux diviseurs
par 2 donc on peut aller jusqu'a 100. Dans cette gamme on trouve aussi des
diviseurs dont le rapport est programmable.
Pour les frequences tres hautes ( au dela de 50Mhz) il existe des chips
prediviseurs juqu'a plusieurs Giga ( utilisés dans les tuners a synthese de
frequence).



--

Alain

"Adrien Gaudel" <adriennospaam_at_stable-boy.net> a écrit dans le message de
news: 46c8436a$0$27407$ba4acef3_at_news.orange.fr...

Mon Aug 20, 2007 3:46 pm   

Adrien Gaudel a écrit :


en fait, cela manque d'explications :

tu veux diviser une frequence, ou bien un nombre en binaire (ou BCD?),
si oui, combien de chiffres?

Mon Aug 20, 2007 5:46 pm   

jj wrote:

Il l'a dit il y a environ 29h:


--


"So all that's left, Is the proof that love's not only blind but deaf."
(FAKE TALES OF SAN FRANCISCO, Arctic Monkeys)