Quel est le moyen le plus rapide pour diviser un nombre entier par 3?
int x = n /3; //<-- make this faster
//for instance
int a = n * 3; //<-- normal integer multiplication
int b = (n << 1) + n; //<-- potentially faster multiplication
C'est le plus rapide que le compilateur de l'optimiser si elle peut en fonction du processeur.
int a;
int b;
a = some value;
b = a /3;
C'est malheureusement ce que je pensais. À la réflexion je pense que ce que vous liant à dire, c'est que le suivant. Si la "valeur" est connu à l'avance le compilateur d'optimiser l'évaluation de la valeur/3. Cependant, je suis intéressé dans le cas où la valeur est déterminée au moment de l'exécution s'avère indépendamment de la valeur connue du compilateur d'optimiser quelque chose de semblable à n * 0x55555556 >> 32 merci La façon la plus simple est souvent le meilleur, n'est-ce pas? Si a est un type signé, mais il est connu pour être positif, (unsigned)a/3 sera probablement plus rapide, car lorsque la division d'un type signé le compilateur va ajouter du code supplémentaire pour s'assurer que les valeurs négatives produisent un truncate-vers-un zéro plutôt que de l'naturellement calculé parqueté de la division de résultat.
Le gars qui a dit "c'est le compilateur" a droite, mais je n'ai pas la "réputation" de mod lui ou un commentaire. J'ai demandé à gcc pour compiler int test(int a) { return a /3; } pour un ix86 et puis démonté la sortie. Juste pour l'intérêt des milieux universitaires, ce qu'il fait est environ en multipliant par 0x55555556 et puis en prenant le haut de 32 bits de 64 bits. Vous pouvez le démontrer à vous-même avec par exemple:
La page de wikipedia sur Montgomery division est dur à lire, mais heureusement, le compilateur les gars ont fait de sorte que vous n'avez pas à.
C'est plus facile à comprendre si vous venez de l'appeler "la réciproque, stockées dans des points fixes" Ce n'est pas de Montgomery division, C'est plus comme l'idée derrière Barrett réduction.
Il y a un moyen plus rapide de le faire si vous connaissez les gammes de valeurs, par exemple, si vous êtes à la division d'un entier signé par 3 et vous connaissez la plage de la valeur à diviser est de 0 à 768, alors vous pouvez multiplier par un facteur et vers la gauche par une puissance de 2 pour que le facteur divisé par 3.
par exemple.
Gamme 0 -> 768
vous pouvez utiliser le déplacement de 10 bits, ce qui, multiplié par 1024, vous voulez diviser par 3, donc votre multiplicateur doit être de 1024 /3 = 341,
de sorte que vous pouvez maintenant utiliser (x * 341) >> 10
(Assurez-vous que le changement est une signature maj si à l'aide de nombres entiers signés), aussi assurez-vous que le changement est en réalité une maj et pas un peu de ROULIS
Cela aura pour effet de diviser la valeur 3, et sera exécuté à environ 1,6 fois la vitesse naturelle de diviser par 3 sur un standard x86 /x64 CPU.
Bien sûr, la seule raison pour laquelle vous pouvez faire cette optimisation lorsque le compilateur cant est parce que le compilateur ne connaît pas la portée maximale de X et, par conséquent, ne peut pas prendre cette décision, mais vous en tant que programmeur peut.
Parfois, il peut même être plus avantageux de déplacer la valeur dans une plus grande valeur et puis faire la même chose, c'est à dire. si vous avez un int d'une gamme complète vous pourriez en faire une valeur de 64 bits et ensuite faire de multiplier et de changement au lieu de diviser par 3.
J'ai dû le faire récemment pour accélérer la vitesse de traitement de l'image, il me fallait trouver le moyen de 3 couches de couleur, chaque canal de couleur, avec une plage d'octets (0 - 255). rouge, vert et bleu.
Au début, j'ai simplement utilisé:
avg = (r + g + b) /3;
(Donc r + g + b a un maximum de 768 et un minimum de 0, parce que chaque canal est un octet 0 - 255)
Après des millions d'itérations de l'ensemble de l'opération a eu 36 millisecondes.
J'ai changé la ligne:
avg = (r + g + b) * 341 >> 10;
Et que l'ai descendu à 22 millisecondes, son incroyable, ce qui peut être fait avec un peu d'ingéniosité.
Cette vitesse a été faite en C#, même si j'avais des optimisations allumé et a été à l'exécution du programme en mode natif sans les informations de débogage et non pas par le biais de l'IDE.
Je vous remercie pour votre explication approfondie. J'étais à côté de la question jusqu'à maintenant. Nice! J'ai eu une division par 5 problème que j'ai été anal sur - moyenne rgba valeurs d'un pixel et ses voisins au nord-sud à l'ouest et de l'est (pauvre homme méchant flou accéléré). J'ai réglé pour une bonne approximation à l'aide de la proportion 50/256 qui est ~0.195. C'est beau, tu peux compter le nombre de cycles d'horloge. p[i] = ((a << 5) + (a << 4) + (a << 1) + a) >> 8; *correction 51/256 -> ~0.199
assez sympa je dois cependant préciser que je suis confiné à quelque chose de x86-ish Je sais que c'est un peu gênant pour pousser un ancien post, mais le lien que tu as donné est MORT(Aaaaaargh!) (je veux dire le premier).
En fonction de votre plate-forme et en fonction de votre compilateur C, une solution native comme juste en utilisant
y = x /3
Peut être rapide ou il peut être terriblement lent (même si la division se fait entièrement dans le matériel, si c'est fait à l'aide d'un DIV instruction, cette instruction est d'environ 3 à 4 fois plus lente qu'une multiplication sur les Processeurs modernes). Très bon compilateurs C avec des options d'optimisation activée peut optimiser cette opération, mais si vous voulez être sûr, vous êtes mieux de l'optimisation de vous-même.
Pour l'optimisation, il est important d'avoir des nombres entiers de taille connue. En C int a pas de taille connue (cela peut varier selon la plateforme et le compilateur!), donc, vous êtes mieux à l'aide de C99 de taille fixe entiers. Le code ci-dessous suppose que vous souhaitez diviser un entier 32 bits non signé par trois et que vous C compilateur sait sur 64 bits des nombres entiers (REMARQUE: Même sur un 32 bits PROCESSEUR de l'architecture de la plupart des compilateurs C peut manipuler des entiers 64 bits amende juste):
Aussi fou que cela puisse paraître, mais la méthode ci-dessus, en effet, que de diviser par 3. Tout ce qu'il faut pour le faire est un seul 64 bits de multiplication et d'une maj (comme je l'ai dit, des multiplications peut-être 3 à 4 fois plus rapide que les divisions de votre PROCESSEUR). Dans la version 64 bits de l'application du présent code sera beaucoup plus rapide que dans un 32 bits (32 bits multiplication de deux 64 bits numéros de prendre 3 multiplications et 3 ajouts sur 32 bits) - toutefois, il pourrait être encore plus rapide qu'une division sur un ordinateur 32 bits.
D'autre part, si votre compilateur est un très bon produit et sait le truc comment optimiser integer division par une constante (dernière version de GCC est le cas, je viens de vérifier), il va générer le code ci-dessus, de toute façon (GCC permettra de créer exactement ce que le code pour "/3" si vous activez au moins optimisation de niveau 1). Pour d'autres compilateurs... vous ne pouvez pas compter ou s'attendre à ce que il va utiliser des trucs comme ça, même si cette méthode est très bien documenté et mentionné partout sur l'Internet.
Problème est qu'il ne fonctionne que pour les constantes, pas de variable. Vous avez toujours besoin de savoir le nombre magique (ici 0xAAAAAAAB) et les opérations correctes après la multiplication (équipes et/ou des ajouts dans la plupart des cas) et à la fois est différente selon le nombre que vous souhaitez diviser par et les deux prennent beaucoup trop de temps PROCESSEUR pour calculer à la volée (ce qui serait plus lent que le matériel de la division). Cependant, il est facile pour un compilateur pour le calcul de ces cours de la compilation (d'où une seconde de plus ou de moins de compiler à peine le temps joue un rôle).
Je souhaite que je pourrais dire au compilateur de ne PAS faire ce genre de chose parfois. Cela fait plus rapidement le code, mais également plus de code. Merci de ne pas le faire, de laisser le compilateur faire. Avec un seul 32 bits multiplier le compilateur va avoir le résultat dans un registre. C'est, il sera dans la mul de débordement du registre EDX. Ainsi, l'optimisation de votre n'est-ce pas, et vous avez maintenant convertis en un seul 32 bits se multiplient dans une version 64 bits de se multiplier et 64 bits de décalage. Il y a ceux qui misent sur le compilateur de faire leur contraire ralentit le code rapide et il y a ceux qui essaient de faire un code rapide, indépendamment du compilateur. Le premier type de personnes de produire du code qui peut échouer horriblement sur certains compilateurs et des plates-formes, le deuxième produit le code qui effectue toujours bonne à très bonne, indépendamment de la plateforme. Le code que j'ai posté ci-dessus n'est pas de produire une version 64 bits de multiplier lors de l'utilisation de GCC sur x86, en fait, dans le seul produit de 32 bits multiplier (depuis un 32 bits se multiplier sur x86 64 bits résultat et GCC sait que). En fait, ces derniers ont tendance à produire du code qui appelle un comportement indéfini et puis coller leurs doigts dans leurs oreilles quand quelqu'un leur dit qu'ils ont tort. Je ne dis pas que ce n'est pas parfois la peine de tenter d'écrire du code qui sera rapide ", même si le compilateur est nul", mais n'importe qui de le faire doit avoir une connaissance approfondie de la norme C un comportement indéfini, la mise en œuvre définies par le comportement, et ce qui est valable et portable. Où faut-il produire un comportement indéfini? La multiplication d'un 64 bits uint 32 bits uint est défini, le décalage de bits de 64 bits uint est défini et coulée de uint64 à uint32 est ainsi définie, au moins dans la norme ISO-C. Est-ce parce que unsigned long long n'est pas défini exactement 64 bits? Eh bien, je vais le corriger pour vous. Autre que cela, montrez-moi un seul, un seul ISO-compilateur C, là où le code ci-dessus ne produisent pas le résultat désiré, ou où un simple / 3 produit d'importantes plus rapidement code (toute l'architecture de la plateforme et est accepté).
Que si vous vraiment ne veux pas de multiplier ou de diviser? Voici est une approximation, je viens de l'inventer. Cela fonctionne parce que (x/3) = (x/4) + (x/12). Mais depuis que (x/12) = (x/4) /3 nous suffit de répéter le processus jusqu'à ce que son assez bon.
#include <stdio.h>
void main()
{
int n = 1000;
int a,b;
a = n >> 2;
b = (a >> 2);
a += b;
b = (b >> 2);
a += b;
b = (b >> 2);
a += b;
b = (b >> 2);
a += b;
printf("a=%d\n", a);
}
Le résultat est de 330. Il pourrait être rendu plus précis à l'aide de b = (b+2)>>2); pour tenir compte de l'arrondi.
Si vous sont autorisé à reproduire, il suffit de choisir une approximation convenable pour (1/3), avec une puissance de 2 diviseur. Par exemple, n * (1/3) ~= n * 43 /128 = (n * 43) >> 7.
Choisissez 2^33 que le diviseur et vous vous retrouvez avec Mecki réponse malheureusement, il ne fonctionnera pas pour les multiples de 3 (il va retourner 0 pour n = 3 et 1 pour n = 6). Vous avez besoin d'un peu plus spécial que les contrôles sur les Hacker plaisir d'avoir quelques erreurs après le passage de l'étape. Malheureux que je ne peux pas comprendre comment cela fonctionne
Je ne sais pas si c'est plus rapide, mais si vous souhaitez utiliser un opérateur au niveau du bit pour effectuer la division binaire, vous pouvez utiliser la touche shift et de soustraire la méthode décrite à cette page:
Ensemble quotient de 0
Aligner à gauche chiffres du dividende et diviseur
Répéter:
Si la partie du dividende ci-dessus le diviseur est supérieur ou égal au diviseur:
Puis soustraire diviseur de la partie du dividende et
Concatentate 1 pour la main droite à la fin de l'quotient
D'autre concatentate 0 à la main droite à la fin de l'quotient
Maj le diviseur d'un droit de la place
Jusqu'à ce dividende est inférieur au diviseur:
quotient est correct, le dividende est reste
ARRÊTER
Je soupçonne que ce n'est pas plus rapide. Il est plus ou moins un algorithme pour faire la division binaire. J'ai enfin trouvé! Il y a longtemps, je suis tombé sur un assembleur 6502 routine de division et d'une certaine manière il a perdu au fil du temps. 6502 a pas de mul/div opcodes, donc c'est le seul moyen. Maintenant je sais! Merci.
Cependant ce n'est pas la tronquer division entière vous pourriez vous attendre.
Il fonctionne correctement si le numéro est déjà divisible par 3, mais il renvoie à un grand nombre, si elle n'est pas.
Par exemple, si vous exécutez sur par exemple 11, il retourne 6148914691236517209. Cela ressemble à une poubelle, mais c'est en fait la réponse correcte: le multiplie par 3 et vous obtenez de retour le 11!
Si vous êtes à la recherche pour la troncature de la division, alors il suffit d'utiliser l'opérateur/. Je doute fortement que vous pouvez obtenir beaucoup plus vite que ça.
Théorie:
64 bits non signé de l'arithmétique est un modulo 2^64 arithmétique.
Cela signifie que pour chaque entier qui est premiers avec la 2^64 module (essentiellement, tous les nombres impairs), il existe un inverse multiplicatif qui vous pouvez utiliser pour multiplier au lieu de la division. Ce nombre magique peut être obtenue par la résolution de l' 3*x + 2^64*y = 1 équation à l'aide de l'Algorithme d'Euclide Étendu.
Si vous voulez vraiment voir cet article sur le division entière, mais il a le mérite académique ... ce serait une application intéressante que réellement nécessaire pour effectuer qui ont bénéficié de ce genre de truc.
vous cherchez quelque chose d'un peu plus pratique, merci bien Pas sûr que ce qui est censé être "académique" ici. À peu près chaque compilateur optimise les divisions par des constantes ou très techniques.
Pour vraiment grande division entière (par exemple, des nombres plus grands que 64 bits), vous pouvez représenter votre numéro de type int[] et effectuer la division très vite par la prise de deux chiffres à la fois et de les diviser par 3. Le reste fera partie de la prochaine deux chiffres et ainsi de suite.
par exemple. 11004 /3 vous dire
11/3 = 3, remaineder = 2 (11-3*3)
20/3 = 6, reste = 2 (20-6*3)
20/3 = 6, reste = 2 (20-6*3)
24/3 = 8, reste = 0
donc le résultat 3668
internal static List<int> Div3(int[] a)
{
int remainder = 0;
var res = new List<int>();
for (int i = 0; i < a.Length; i++)
{
var val = remainder + a[i];
var div = val/3;
remainder = 10*(val%3);
if (div > 9)
{
res.Add(div/10);
res.Add(div%10);
}
else
res.Add(div);
}
if (res[0] == 0) res.RemoveAt(0);
return res;
}
Le truc cool, c'est que c'est un naïf matériel de mise en œuvre de ce problème. Le moins cool, c'est qu'en fait cela ne peut pas être plus rapide que tout le matériel de mise en œuvre, à moins que le matériel de mise en œuvre de la CPU est à essayer.
C'est le plus rapide que le compilateur de l'optimiser si elle peut en fonction du processeur.
À la réflexion je pense que ce que vous liant à dire, c'est que le suivant. Si la "valeur" est connu à l'avance le compilateur d'optimiser l'évaluation de la valeur/3. Cependant, je suis intéressé dans le cas où la valeur est déterminée au moment de l'exécution
s'avère indépendamment de la valeur connue du compilateur d'optimiser quelque chose de semblable à n * 0x55555556 >> 32 merci
La façon la plus simple est souvent le meilleur, n'est-ce pas?
Si
aest un type signé, mais il est connu pour être positif,(unsigned)a/3sera probablement plus rapide, car lorsque la division d'un type signé le compilateur va ajouter du code supplémentaire pour s'assurer que les valeurs négatives produisent un truncate-vers-un zéro plutôt que de l'naturellement calculé parqueté de la division de résultat.OriginalL'auteur KPexEA
Le gars qui a dit "c'est le compilateur" a droite, mais je n'ai pas la "réputation" de mod lui ou un commentaire. J'ai demandé à gcc pour compiler int test(int a) { return a /3; } pour un ix86 et puis démonté la sortie. Juste pour l'intérêt des milieux universitaires, ce qu'il fait est environ en multipliant par 0x55555556 et puis en prenant le haut de 32 bits de 64 bits. Vous pouvez le démontrer à vous-même avec par exemple:
La page de wikipedia sur Montgomery division est dur à lire, mais heureusement, le compilateur les gars ont fait de sorte que vous n'avez pas à.
Ce n'est pas de Montgomery division, C'est plus comme l'idée derrière Barrett réduction.
OriginalL'auteur Martin Dorey
Il y a un moyen plus rapide de le faire si vous connaissez les gammes de valeurs, par exemple, si vous êtes à la division d'un entier signé par 3 et vous connaissez la plage de la valeur à diviser est de 0 à 768, alors vous pouvez multiplier par un facteur et vers la gauche par une puissance de 2 pour que le facteur divisé par 3.
par exemple.
Gamme 0 -> 768
vous pouvez utiliser le déplacement de 10 bits, ce qui, multiplié par 1024, vous voulez diviser par 3, donc votre multiplicateur doit être de 1024 /3 = 341,
de sorte que vous pouvez maintenant utiliser (x * 341) >> 10
(Assurez-vous que le changement est une signature maj si à l'aide de nombres entiers signés), aussi assurez-vous que le changement est en réalité une maj et pas un peu de ROULIS
Cela aura pour effet de diviser la valeur 3, et sera exécuté à environ 1,6 fois la vitesse naturelle de diviser par 3 sur un standard x86 /x64 CPU.
Bien sûr, la seule raison pour laquelle vous pouvez faire cette optimisation lorsque le compilateur cant est parce que le compilateur ne connaît pas la portée maximale de X et, par conséquent, ne peut pas prendre cette décision, mais vous en tant que programmeur peut.
Parfois, il peut même être plus avantageux de déplacer la valeur dans une plus grande valeur et puis faire la même chose, c'est à dire. si vous avez un int d'une gamme complète vous pourriez en faire une valeur de 64 bits et ensuite faire de multiplier et de changement au lieu de diviser par 3.
J'ai dû le faire récemment pour accélérer la vitesse de traitement de l'image, il me fallait trouver le moyen de 3 couches de couleur, chaque canal de couleur, avec une plage d'octets (0 - 255). rouge, vert et bleu.
Au début, j'ai simplement utilisé:
avg = (r + g + b) /3;
(Donc r + g + b a un maximum de 768 et un minimum de 0, parce que chaque canal est un octet 0 - 255)
Après des millions d'itérations de l'ensemble de l'opération a eu 36 millisecondes.
J'ai changé la ligne:
avg = (r + g + b) * 341 >> 10;
Et que l'ai descendu à 22 millisecondes, son incroyable, ce qui peut être fait avec un peu d'ingéniosité.
Cette vitesse a été faite en C#, même si j'avais des optimisations allumé et a été à l'exécution du programme en mode natif sans les informations de débogage et non pas par le biais de l'IDE.
Nice! J'ai eu une division par 5 problème que j'ai été anal sur - moyenne rgba valeurs d'un pixel et ses voisins au nord-sud à l'ouest et de l'est (pauvre homme méchant flou accéléré). J'ai réglé pour une bonne approximation à l'aide de la proportion 50/256 qui est ~0.195. C'est beau, tu peux compter le nombre de cycles d'horloge.
p[i] = ((a << 5) + (a << 4) + (a << 1) + a) >> 8;*correction 51/256 -> ~0.199
OriginalL'auteur Aaron Murgatroyd
Voir Comment Diviser Par 3 pour une discussion étendue de manière plus efficace en divisant par 3, axée sur des FPGA opérations arithmétiques.
Aussi pertinent:
Je sais que c'est un peu gênant pour pousser un ancien post, mais le lien que tu as donné est MORT (Aaaaaargh!) (je veux dire le premier).
OriginalL'auteur Jay
En fonction de votre plate-forme et en fonction de votre compilateur C, une solution native comme juste en utilisant
Peut être rapide ou il peut être terriblement lent (même si la division se fait entièrement dans le matériel, si c'est fait à l'aide d'un DIV instruction, cette instruction est d'environ 3 à 4 fois plus lente qu'une multiplication sur les Processeurs modernes). Très bon compilateurs C avec des options d'optimisation activée peut optimiser cette opération, mais si vous voulez être sûr, vous êtes mieux de l'optimisation de vous-même.
Pour l'optimisation, il est important d'avoir des nombres entiers de taille connue. En C int a pas de taille connue (cela peut varier selon la plateforme et le compilateur!), donc, vous êtes mieux à l'aide de C99 de taille fixe entiers. Le code ci-dessous suppose que vous souhaitez diviser un entier 32 bits non signé par trois et que vous C compilateur sait sur 64 bits des nombres entiers (REMARQUE: Même sur un 32 bits PROCESSEUR de l'architecture de la plupart des compilateurs C peut manipuler des entiers 64 bits amende juste):
Aussi fou que cela puisse paraître, mais la méthode ci-dessus, en effet, que de diviser par 3. Tout ce qu'il faut pour le faire est un seul 64 bits de multiplication et d'une maj (comme je l'ai dit, des multiplications peut-être 3 à 4 fois plus rapide que les divisions de votre PROCESSEUR). Dans la version 64 bits de l'application du présent code sera beaucoup plus rapide que dans un 32 bits (32 bits multiplication de deux 64 bits numéros de prendre 3 multiplications et 3 ajouts sur 32 bits) - toutefois, il pourrait être encore plus rapide qu'une division sur un ordinateur 32 bits.
D'autre part, si votre compilateur est un très bon produit et sait le truc comment optimiser integer division par une constante (dernière version de GCC est le cas, je viens de vérifier), il va générer le code ci-dessus, de toute façon (GCC permettra de créer exactement ce que le code pour "/3" si vous activez au moins optimisation de niveau 1). Pour d'autres compilateurs... vous ne pouvez pas compter ou s'attendre à ce que il va utiliser des trucs comme ça, même si cette méthode est très bien documenté et mentionné partout sur l'Internet.
Problème est qu'il ne fonctionne que pour les constantes, pas de variable. Vous avez toujours besoin de savoir le nombre magique (ici 0xAAAAAAAB) et les opérations correctes après la multiplication (équipes et/ou des ajouts dans la plupart des cas) et à la fois est différente selon le nombre que vous souhaitez diviser par et les deux prennent beaucoup trop de temps PROCESSEUR pour calculer à la volée (ce qui serait plus lent que le matériel de la division). Cependant, il est facile pour un compilateur pour le calcul de ces cours de la compilation (d'où une seconde de plus ou de moins de compiler à peine le temps joue un rôle).
Merci de ne pas le faire, de laisser le compilateur faire. Avec un seul 32 bits multiplier le compilateur va avoir le résultat dans un registre. C'est, il sera dans la mul de débordement du registre EDX. Ainsi, l'optimisation de votre n'est-ce pas, et vous avez maintenant convertis en un seul 32 bits se multiplient dans une version 64 bits de se multiplier et 64 bits de décalage.
Il y a ceux qui misent sur le compilateur de faire leur contraire ralentit le code rapide et il y a ceux qui essaient de faire un code rapide, indépendamment du compilateur. Le premier type de personnes de produire du code qui peut échouer horriblement sur certains compilateurs et des plates-formes, le deuxième produit le code qui effectue toujours bonne à très bonne, indépendamment de la plateforme. Le code que j'ai posté ci-dessus n'est pas de produire une version 64 bits de multiplier lors de l'utilisation de GCC sur x86, en fait, dans le seul produit de 32 bits multiplier (depuis un 32 bits se multiplier sur x86 64 bits résultat et GCC sait que).
En fait, ces derniers ont tendance à produire du code qui appelle un comportement indéfini et puis coller leurs doigts dans leurs oreilles quand quelqu'un leur dit qu'ils ont tort. Je ne dis pas que ce n'est pas parfois la peine de tenter d'écrire du code qui sera rapide ", même si le compilateur est nul", mais n'importe qui de le faire doit avoir une connaissance approfondie de la norme C un comportement indéfini, la mise en œuvre définies par le comportement, et ce qui est valable et portable.
Où faut-il produire un comportement indéfini? La multiplication d'un 64 bits uint 32 bits uint est défini, le décalage de bits de 64 bits uint est défini et coulée de uint64 à uint32 est ainsi définie, au moins dans la norme ISO-C. Est-ce parce que unsigned long long n'est pas défini exactement 64 bits? Eh bien, je vais le corriger pour vous. Autre que cela, montrez-moi un seul, un seul ISO-compilateur C, là où le code ci-dessus ne produisent pas le résultat désiré, ou où un simple / 3 produit d'importantes plus rapidement code (toute l'architecture de la plateforme et est accepté).
OriginalL'auteur Mecki
Que si vous vraiment ne veux pas de multiplier ou de diviser? Voici est une approximation, je viens de l'inventer. Cela fonctionne parce que (x/3) = (x/4) + (x/12). Mais depuis que (x/12) = (x/4) /3 nous suffit de répéter le processus jusqu'à ce que son assez bon.
Le résultat est de 330. Il pourrait être rendu plus précis à l'aide de b = (b+2)>>2); pour tenir compte de l'arrondi.
Si vous sont autorisé à reproduire, il suffit de choisir une approximation convenable pour (1/3), avec une puissance de 2 diviseur. Par exemple, n * (1/3) ~= n * 43 /128 = (n * 43) >> 7.
Cette technique est très utile dans la L'Indiana.
malheureusement, il ne fonctionnera pas pour les multiples de 3 (il va retourner 0 pour n = 3 et 1 pour n = 6). Vous avez besoin d'un peu plus spécial que les contrôles sur les
Hacker plaisir d'avoir quelques erreurs après le passage de l'étape. Malheureux que je ne peux pas comprendre comment cela fonctionne
OriginalL'auteur Steve Hanov
Je ne sais pas si c'est plus rapide, mais si vous souhaitez utiliser un opérateur au niveau du bit pour effectuer la division binaire, vous pouvez utiliser la touche shift et de soustraire la méthode décrite à cette page:
J'ai enfin trouvé! Il y a longtemps, je suis tombé sur un assembleur 6502 routine de division et d'une certaine manière il a perdu au fil du temps. 6502 a pas de mul/div opcodes, donc c'est le seul moyen. Maintenant je sais! Merci.
OriginalL'auteur Mark Cidade
Pour 64 bits:
Cependant ce n'est pas la tronquer division entière vous pourriez vous attendre.
Il fonctionne correctement si le numéro est déjà divisible par 3, mais il renvoie à un grand nombre, si elle n'est pas.
Par exemple, si vous exécutez sur par exemple 11, il retourne 6148914691236517209. Cela ressemble à une poubelle, mais c'est en fait la réponse correcte: le multiplie par 3 et vous obtenez de retour le 11!
Si vous êtes à la recherche pour la troncature de la division, alors il suffit d'utiliser l'opérateur/. Je doute fortement que vous pouvez obtenir beaucoup plus vite que ça.
Théorie:
64 bits non signé de l'arithmétique est un modulo 2^64 arithmétique.
Cela signifie que pour chaque entier qui est premiers avec la 2^64 module (essentiellement, tous les nombres impairs), il existe un inverse multiplicatif qui vous pouvez utiliser pour multiplier au lieu de la division. Ce nombre magique peut être obtenue par la résolution de l'
3*x + 2^64*y = 1équation à l'aide de l'Algorithme d'Euclide Étendu.OriginalL'auteur Calmarius
Si vous voulez vraiment voir cet article sur le division entière, mais il a le mérite académique ... ce serait une application intéressante que réellement nécessaire pour effectuer qui ont bénéficié de ce genre de truc.
Pas sûr que ce qui est censé être "académique" ici. À peu près chaque compilateur optimise les divisions par des constantes ou très techniques.
OriginalL'auteur Rob Walker
Pour vraiment grande division entière (par exemple, des nombres plus grands que 64 bits), vous pouvez représenter votre numéro de type int[] et effectuer la division très vite par la prise de deux chiffres à la fois et de les diviser par 3. Le reste fera partie de la prochaine deux chiffres et ainsi de suite.
par exemple. 11004 /3 vous dire
11/3 = 3, remaineder = 2 (11-3*3)
20/3 = 6, reste = 2 (20-6*3)
20/3 = 6, reste = 2 (20-6*3)
24/3 = 8, reste = 0
donc le résultat 3668
OriginalL'auteur Carlo V. Dango
Facile le calcul ... au plus n itérations où n est le nombre de bits:
OriginalL'auteur Albert Gonzalez
Une table de recherche approche permettrait aussi d'être plus rapide dans certaines architectures.
OriginalL'auteur Luke