Repository 32bit  Forum
Repository 64bit  Wiki

[C] Estrarre le cifre di un numero

Forum dedicato alla programmazione.

Moderatore: Staff

Regole del forum
1) Citare in modo preciso il linguaggio di programmazione usato.
2) Se possibile portare un esempio del risultato atteso.
3) Leggere attentamente le risposte ricevute.
4) Scrivere i messaggi con il colore di default, evitare altri colori.
5) Scrivere in Italiano o in Inglese, se possibile grammaticalmente corretto, evitate stili di scrittura poco chiari, quindi nessuna abbreviazione tipo telegramma o scrittura stile SMS o CHAT.
6) Appena registrati è consigliato presentarsi nel forum dedicato.

La non osservanza delle regole porta a provvedimenti di vari tipo da parte dello staff, in particolare la non osservanza della regola 5 porta alla cancellazione del post e alla segnalazione dell'utente. In caso di recidività l'utente rischia il ban temporaneo.

[C] Estrarre le cifre di un numero

Messaggioda boh » gio giu 06, 2013 13:16

Ciao a tutti!
Sto attualmente lavorando su un progetto per implementare l'algoritmo di exact division (Ref: Jebelean - An algorithm for exact division, pag. 4).
L'algoritmo in sè non è difficile, ma lo è di più implementarlo in modo efficiente.
In particolare, ho la necessità di estrarre iterativamente le cifre meno significative del dividendo per poter così calcolare le corrispondenti meno significative del quoziente.
Mi sto documentando sulla libreria gmp, ma non riesco a trovare nulla che riguardi il mio problema.
Vorrei evitare la soluzione classica di dividere il numero per 10 per poi scartare il decimale con l'assegnamento a integer.

Qualcuno sa darmi qualche dritta su cosa cercare? O se conosce gmp, che funzione potrebbe fare al caso mio?

P.S: anche mettere il numero in un array di caratteri non credo sia una buona soluzione, ma non ne sono certo.
"Be yourself. Everyone else is already taken." ~ Oscar Wilde
Avatar utente
boh
Linux 2.6
Linux 2.6
 
Messaggi: 953
Iscritto il: gio set 15, 2005 23:00
Località: Milano
Slackware: 14.1 (x64)
Kernel: 3.14.1
Desktop: KDE 4.13.3

Re: [C] Estrarre le cifre di un numero

Messaggioda masalapianta » gio giu 06, 2013 15:44

boh ha scritto:Ciao a tutti!
Sto attualmente lavorando su un progetto per implementare l'algoritmo di exact division (Ref: Jebelean - An algorithm for exact division, pag. 4).
L'algoritmo in sè non è difficile, ma lo è di più implementarlo in modo efficiente.
In particolare, ho la necessità di estrarre iterativamente le cifre meno significative del dividendo per poter così calcolare le corrispondenti meno significative del quoziente.
Mi sto documentando sulla libreria gmp, ma non riesco a trovare nulla che riguardi il mio problema.
Vorrei evitare la soluzione classica di dividere il numero per 10 per poi scartare il decimale con l'assegnamento a integer.

perchè no? in questi casi si usa proprio l'operatore modulo (se trovi qualche libreria che fa quel che chiedi, andando a vedere il sorgente scoprirai che quasi sicuramente usa questo metodo)
P.S: anche mettere il numero in un array di caratteri non credo sia una buona soluzione, ma non ne sono certo.

quindi non vuoi neanche convertire il numero in stringa (con atoi() o equivalente), smanettarlo e poi riconvertire in integer con snprintf()? allora temo che ti resti solo la bacchetta magica e poco altro.
Avatar utente
masalapianta
Iper Master
Iper Master
 
Messaggi: 2775
Iscritto il: dom lug 24, 2005 23:00
Località: Roma
Nome Cognome: famoso porco
Kernel: uname -r
Desktop: awesome
Distribuzione: Debian

Re: [C] Estrarre le cifre di un numero

Messaggioda Vito » gio giu 06, 2013 15:45

boh ha scritto:Vorrei evitare la soluzione classica di dividere il numero per 10 per poi scartare il decimale con l'assegnamento a integer.


Confesso di aver pensato subito a questa cosa non appena ho letto il titolo della discussione.
"Stat rosa pristina nomina, nomina nuda tenemus." [ Umberto Eco - Il nome della rosa]

"Faber est suae quisque fortunae ." [ Appio Claudio Cieco]
Avatar utente
Vito
Staff
Staff
 
Messaggi: 4135
Iscritto il: mar dic 05, 2006 17:28
Località: Augsburg (DE)
Nome Cognome: Vito
Slackware: 64 14.0 multilib
Kernel: 3.2.29-xps
Desktop: KDE 4.10.2
Distribuzione: Linux Mint 17

Re: [C] Estrarre le cifre di un numero

Messaggioda brg » gio giu 06, 2013 17:56

L'unica alternativa che ti rimane a questo punto è implementare l'algoritmo in base 2 ed usare gli operatori logici, che probabilmente è anche la soluzione più efficace da un punto di vista computazionale. Se sei limitato alla base 10 allora divisione e resto è meglio, ma capisco che non abbia senso in un algoritmo che implementa l'operazione di divisione, quindi dovresti usare atoi (standard in C99), che però sarà sempre un passaggio più lento che usare l'operazione di divisione standard del C. Oppure ti fai la tua funzioncina in assembly, scegli tu.
Avatar utente
brg
Linux 2.4
Linux 2.4
 
Messaggi: 262
Iscritto il: sab mar 12, 2011 14:20
Località: Montecatini
Slackware: 14.1
Kernel: 3.10.17
Desktop: KDE4

Re: [C] Estrarre le cifre di un numero

Messaggioda boh » gio giu 06, 2013 18:19

Grazie per le risposte!

@masalapianta: sono dubbioso sull'uso di modulo/divisione perchè sto implementando una divisione ottimizzata e farlo usando la divisione non mi sembra che abbia senso; oltretutto si parla di dividere per 10 un numero che potrebbe avere anche 100 o più cifre, non vorrei rallentasse troppo. Per l'array non l'ho escluso a priori, ma mi sembra una soluzione lenta per il fatto che il numero memorizzato nell'array va poi modificato attraverso una sottrazione e quindi dovrei riconvertirlo in numero per poi riportarlo nell'array ed estrarre la nuova ultima cifra.

@brg: in base 2 posso lavorare sui bit per estrarre il meno significativo e fare uno shift right per eliminare l'ultima, giusto? Quindi avrebbe senso prendere i due numeri in decimale, convertirli in binario, fare la divisione ottimizzata e restituire il quoziente ancora in decimale?
L'assemlby eviterei, non lo conosco molto bene 8-[
"Be yourself. Everyone else is already taken." ~ Oscar Wilde
Avatar utente
boh
Linux 2.6
Linux 2.6
 
Messaggi: 953
Iscritto il: gio set 15, 2005 23:00
Località: Milano
Slackware: 14.1 (x64)
Kernel: 3.14.1
Desktop: KDE 4.13.3

Re: [C] Estrarre le cifre di un numero

Messaggioda brg » gio giu 06, 2013 18:47

Non hai da convertire alcunché, i numeri elaborati da un calcolatore sono già tutti binari. Io farei una cosa del genere, ammesso che tu stia usando degli interi e non dei numeri in virgola mobile:

Codice: Seleziona tutto
!!!PSEUDOCODICE!!!
/* numero è la varibile da cui devi estrarre la cifra */
int numero

/* fai una copia */
int temp = numero

/* estrai l'ultima cifra binaria */
temp &= 1

/* "dividi" per due, cioè scarti l'ultima cifra binaria*/
numero = numero >> 1

/* ora temp contiene l'ultima cifra,
 *  mentre numero è diviso per due
 */



Puoi fare questa cosa con qualunque base che sia potenza di 2, ad es.: temp = temp & 3; numero = numero >> 2;
Avatar utente
brg
Linux 2.4
Linux 2.4
 
Messaggi: 262
Iscritto il: sab mar 12, 2011 14:20
Località: Montecatini
Slackware: 14.1
Kernel: 3.10.17
Desktop: KDE4

Re: [C] Estrarre le cifre di un numero

Messaggioda 414N » sab giu 08, 2013 9:34

boh ha scritto:[..] oltretutto si parla di dividere per 10 un numero che potrebbe avere anche 100 o più cifre, non vorrei rallentasse troppo.

Interessante... Servirebbero tra i 256 e i 512 bit per mantenere un intero da circa 100 cifre in memoria (ovviamente considerandolo senza segno, altrimenti si raddoppia).
Domanda: stai applicando questo algoritmo, prendendo come base β (radix) 10? In caso affermativo, temo tu stia commettendo un errore di fondo, in quanto l'algoritmo richiede che β sia un numero primo per garantire l'esistenza di un a' (che non sarebbe garantita in caso contrario).
Ad ogni modo, esiste anche un libreria per l'ottimizzazione delle divisioni a runtime, ovvero libdivide.
Avatar utente
414N
Iper Master
Iper Master
 
Messaggi: 2882
Iscritto il: mer feb 13, 2008 16:19
Località: Bulagna
Slackware: 14.0 (x64)
Kernel: 3.2.29
Desktop: LXDE

Re: [C] Estrarre le cifre di un numero

Messaggioda boh » sab giu 08, 2013 13:43

Sì, l'algoritmo è quello e sì, la base deve essere prima.
Più che un errore è un'omissione, perchè se la base non è prima, l'ultima cifra del dividendo e la base devono essere coprimi per poter applicare l'algoritmo.
Attualmente sono anche propenso a cambiare progetto, perchè non trovo una possibilità di parallelizzazione senza l'uso di dispositivi hardware dedicati (systolic array).
In ogni caso, mi interessa comunque proseguire la discussione.

Libdivide potrebbe essere una buona soluzione per l'estrazione della cifra. Se la base è diversa dalla 10, i numeri è possibili inserirli comunque come se fossero decimali, anche se poi la base è diversa (es: 2555 mod 7 --> inserisco 2555 e poi l'algoritmo lo tratterà con la base specificata; dovrò comunque estrarre almeno la metà delle cifre), o sbaglio qualcosa?

@brg: la rappresentazione è binaria, ma in un numero come quello sopra io devo estrarre comunque 5 e questo non è rappresentato dall'ultima cifra binaria, o sto sbagliando qualcosa anche qui?
"Be yourself. Everyone else is already taken." ~ Oscar Wilde
Avatar utente
boh
Linux 2.6
Linux 2.6
 
Messaggi: 953
Iscritto il: gio set 15, 2005 23:00
Località: Milano
Slackware: 14.1 (x64)
Kernel: 3.14.1
Desktop: KDE 4.13.3

Re: [C] Estrarre le cifre di un numero

Messaggioda brg » sab giu 08, 2013 17:31

Allora, m'è caduta la connessione mentre stavo scrivendo un esempio, tuttavia il succo è questo: estrai 5 se la tua base è maggiore di 5, se sei in base 2 estrai 1 ed il risultato finale non cambia, hai solamente bisogno di fare un numero diverso di passaggi. Se devi ad esempio dividere 6 per 3 in base 2, fai due passaggi (K = lung(0b110) - lung(0b11) + 1 == 2), in base 8 ne fai uno solo (K = lung(06) - lung(03) + 1 == 1). Tuttavia in entrambi i casi ottieni 2 come risultato: nel primo caso 2 è 0b10 e contiene due cifre (per cui necessiti di due passaggi), mentre nel secondo caso 2 è 02 (il C identifica lo 0 iniziale come un identificatore di base 8 ) e contiene una cifra sola, che ricavi in un solo passaggio.

P.S. ho usato le notazioni binarie ed ottali per mostrare le differenze, ma usare una base non richiede di usarne la notazione. Puoi tranquillamente usare numeri in notazione decimale e implementare l'algoritmo in base 2. Tuttavia da quel che ho visto, le uniche soluzioni sensate sono quelle di usare come basi delle potenze di due. Se vuoi mi dilungo su questo punto, ma mi pare abbastanza ovvio.
Avatar utente
brg
Linux 2.4
Linux 2.4
 
Messaggi: 262
Iscritto il: sab mar 12, 2011 14:20
Località: Montecatini
Slackware: 14.1
Kernel: 3.10.17
Desktop: KDE4


Torna a Programmazione

Chi c’è in linea

Visitano il forum: Nessuno e 0 ospiti