C++ Separate Digits: No Division Needed

[Skainstein]

I don't know much of programming but i know a few things...so please be gentle on me
I need help (in C++) with separating the diggits of a number without using any divisions (no '%10', no '/10', etc), just something that reads the number and gives me the diggits. don't know if it helps but those numbers which i want to separate, are in a loop. I would really appreciate your help people. an example would be great. thx.

 

[chroot]

What do you mean by "reads the number?" Are you obtaining a number from the keyboard? And what do you mean by numbers being "in a loop?"

You need to ask clearer questions.

- Warren

 

[Timo]

Copy it to a string .

No honestly, it would probably help saying what kind of numbers you're talking about (type and range), why you don't want to use /10 and %10, what you need it for, what the relevant part of your program looks like (or is supposed to look like),...

 

[rcgldr]

A very large array of pointers to strings representing the digits of the index into the arrray of pointers would work. With a mere 1,188,888,826 bytes (1.189GB) of ram, 4 bytes per pointer, 1 byte per digit, using sequential pointers to calculate string lengths (no string terminators), you could quickly convert the numbers from 0 to 99,999,999 into strings.

 

[las3rjock]

I agree that the original poster needs to be more precise in defining the problem. Does "number" mean that the input is an integer, a floating-point number, or possibly either type? I also think that it's rather strange that you would not be able to use division or modular arithmetic, but under those restrictions, I agree with Timo that your best bet is to convert the number into a string.

 

[las3rjock]

A very large array of pointers to strings representing the digits of the index into the arrray of pointers would work. With a mere 1,188,888,826 bytes (1.189GB) of ram, 4 bytes per pointer, 1 byte per digit, using sequential pointers to calculate string lengths (no string terminators), you could quickly convert the numbers from 0 to 99,999,999 into strings.

This is quite possibly the most expensive and non-obvious digit-extraction algorithm I've ever heard of...

 

[Skainstein]

ok. I'm sorry. i'll be more specific. the program I'm doing is supposed to test if numbers are primes or not but without any need of divisons. for those who know, the divisions are what takes longer to calculate so i don't want to use them. it stars from, the user uses the keybord to say what's the maximum point for the program to run, then the program does it all by itself, running from 0 (or 1) to that number. i was thinking of something like cin.get(), then puting the numbers into an array or something. thanks for ur quick replys. PS: the numbers can become really large, like 100 digits and more, but for now their just until 10 digits. and...i hope its not asking much but could u give an example.

 

[Skainstein]

i've read the posts where it says to put numbers into a string and it seems to be a good idea...i just don't know how to do that.

 

[CRGreathouse]

ok. I'm sorry. i'll be more specific. the program I'm doing is supposed to test if numbers are primes or not but without any need of divisons. for those who know, the divisions are what takes longer to calculate so i don't want to use them. it stars from, the user uses the keybord to say what's the maximum point for the program to run, then the program does it all by itself, running from 0 (or 1) to that number. i was thinking of something like cin.get(), then puting the numbers into an array or something. thanks for ur quick replys. PS: the numbers can become really large, like 100 digits and more, but for now their just until 10 digits. and...i hope its not asking much but could u give an example.

Reading a number from the keyboard and converting it to an integer (or longlongint or whatever) shouldn't take much time compared to checking a 100-digit number for primality.

 

[Timo]

- Conversion of integers to strings is not much of a problem. A c++ solution is piping the number into a stringstream and then obtaining it as a string from there. Another more c-like version is using printf(). Should be easy finding examples by using google (keyword being something like " "c++" integer string conversion").
- The usage of %x and /x is probably not slow compared to anything similar you're going to write yourself.
- Most importantly: With ever-increasing size of the numbers you want to check you will sooner or later run into the problem how to store the numbers (integers are relatively limited in their range) - and that's only the first problem you run into. One possibility is storing the numbers in a string all the time and defining the appropriate mathematical operations (addition, division) on string objects. That's a solution but -performance wise- far from being a good one.

 

[chroot]

You don't need stringstreams or any other garbage. C'mon. A "number," as typed by the user on a keyboard, is just a string of characters. It's a word.

Use something like this:

char number[20];
cin >> number;

The first digit is number[0], the second digit is number[1], etc.

I still have no idea how this is going to help you test for primality, though.

- Warren

 

[Timo]

[...]I still have no idea how this is going to help you test for primality, though.

That's the point where your statement claiming "you can simply use a character array" breaks down (sidenote: Imho a std::string object is preferrable over a character array in almost all cases). As he said, he's going to loop from 2 to the input number, meaning that if he's keeping the input as a char array he needs to either compare the loop-counter with the number or define/program mathematical operations on the character array. Pretty much the same is true for checking if the current number is prime.

 

[chroot]

Okay, so use atoi(), or the frustratingly stupid C++ equivalent.

So why is he going to use the number as a loop condition, but then also look at individual digits of it? Perhaps I don't understand the "algorithm" he's attempting to build.

- Warren

 

[Skainstein]

all right, so what do u guys think: for number with, for example 20 digits, is it faster for the computer to make %10 or %100 (whatever), or to separate the digits other way than that? maybe it's a stupid question but let me remind u...i'm a n00b at this things :P

don't feel bad not to understand the algorithm...i invented it :D that's why i need this program. i need to know if it really works.

 

[chroot]

Separating the digits requires essentially zero time. After all, they're typed in by the user as separate digits!

- Warren

 

[Skainstein]

no, no, no! that's what I've written before (u didn't read it maybe). the only number i type is the maximum value of my loop which starts in 0. now imagine i say to the program the maximum value is 1000000. it'll start with zero, and all by itself will get to 999999 and finally 1000000. now if it's in...12345, i didn't type that number. got it? it must separate the digits of the numbers which itself increases with the loop.

 

[chroot]

Okay. Well, all of the methods used to convert integers into decimal strings involve divisions, which appears to be against your philosophy.

I would suggest simply using itoa() or sprintf().

- Warren

 

[Skainstein]

So what ur telling me is that the other ways to do what i need are dependent on those %10, etc?

i don't know what itoa() is :P. is it something like cin.get()?

 

[chroot]

Yes, itoa() and sprintf() are internally going to use divisions.

Use google to learn more.

- Warren

 

[Skainstein]

it's what I've been doing :P sorry for being such a pain in the ass

 

[-Job-]

Since, you're counting up, you could save work by keeping track of the digits as you go instead of extracting all of the digits each time.
Keep an array which will hold the digits, initialized to [0, 0, 0, 0, 0, 0, 0, 0, 0]. Then in your loop you manually update the digits at each increment (check for 9s and propagate 1s).

 

[chroot]

-Job-,

This is the way many people construct their first arbitrary-precision arithmetic code: they use a number represented by a string of ASCII digits, and then write their own grade-school algorithms to manipulate them.

Of course, if Skainstein wants to use the number in any other kind of mathematical way, he's going to have to convert it to an integer in every loop, too.

You could maintain two "representations" of the number simultaneously -- an integer representation, and a digit-string representation -- and increment them both at the same time.

- Warren

 

[rcgldr]

Okay. Well, all of the methods used to convert integers into decimal strings involve divisions, which appears to be against your philosophy.

My 1.189GB string table didn't require division. Also repetitive subtractions of powers of 10 could be used.

Then again, if you just hate division, you could use the Newton-Raphson algorithm to find 1/x then multiply. You can find a basic description here. Optimized versions of this algorithm are used on DSP's that don't have a divide instruction, but do have a very fast multiply instruction.

http://en.wikipedia.org/wiki/Division_(digital)

they use a number represented by a string of ASCII digits, and then write their own grade-school algorithms to manipulate them.

Some computers, like IBM mainframes, include the ability to do math on variable length numbers that use 4 bits per decimal digit. The Intel CPU's can only add and subtract a one byte pair of nibbles, but utilize the carry flag so the math can be extended.

For generic variable length binary math, this website includes a library and source code:

http://www.apfloat.org