C++ Separate Digits: No Division Needed

  • C/C++
  • Thread starter Skainstein
  • Start date
  • Tags
    C++
In summary, the conversation is about a request for help with a C++ program that separates digits of a number without using division or modular arithmetic. The original poster is unclear about the type and range of numbers and why those operations cannot be used. Various suggestions are made, including converting the number into a string, but the purpose of the program (testing for primality) is questioned. The conversation also discusses the potential difficulties and limitations of using a character array for storing and manipulating the numbers.
  • #1
Skainstein
8
0
I don't know much of programming but i know a few things...so please be gentle on me o:)
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. :cool:
 
Last edited:
Technology news on Phys.org
  • #2
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
 
  • #3
Copy it to a string :biggrin:.

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),...
 
  • #4
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.
 
Last edited:
  • #5
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.
 
Last edited:
  • #6
Jeff Reid said:
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... :biggrin:
 
Last edited:
  • #7
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.
 
Last edited:
  • #8
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.
 
  • #9
Skainstein said:
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.
 
  • #10
- 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.
 
  • #11
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
 
  • #12
chroot said:
[...]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.
 
  • #13
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
 
  • #14
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.
 
Last edited:
  • #15
Separating the digits requires essentially zero time. After all, they're typed in by the user as separate digits!

- Warren
 
  • #16
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.
 
  • #17
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
 
  • #18
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()?
 
  • #19
Yes, itoa() and sprintf() are internally going to use divisions.

Use google to learn more.

- Warren
 
  • #20
it's what I've been doing :P sorry for being such a pain in the ass
 
  • #21
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).
 
  • #22
-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
 
  • #23
chroot said:
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
 
Last edited:

What is "C++ Separate Digits: No Division Needed"?

"C++ Separate Digits: No Division Needed" is a programming concept that involves manipulating an integer to separate its individual digits without using the division operator.

Why is it important to learn how to separate digits in C++ without division?

Separating digits in C++ without division can be useful in many applications, such as data analysis and encryption, where operations on individual digits are required. Additionally, it can improve your understanding of C++ and make you a more versatile programmer.

How do you separate digits in C++ without using the division operator?

One approach is to use the modulus operator (%) to obtain the remainder when dividing by 10. This remainder will be the last digit of the integer. Then, you can divide the integer by 10 and repeat the process until all digits have been separated.

Can you provide an example of separating digits in C++ without division?

Yes, for example, if we have the integer 12345, we can use the modulus operator to obtain the remainder of 12345 / 10, which is 5. Then, we divide 12345 by 10, which gives us 1234, and we repeat the process until we have all the digits separated: 5, 4, 3, 2, 1.

Are there any other ways to separate digits in C++ without using division?

Yes, there are other approaches, such as converting the integer to a string and then accessing each character individually. However, using the modulus operator is a more efficient and commonly used method.

Similar threads

  • Programming and Computer Science
Replies
12
Views
1K
  • Programming and Computer Science
Replies
12
Views
1K
  • Programming and Computer Science
Replies
17
Views
1K
  • Programming and Computer Science
Replies
15
Views
4K
  • Programming and Computer Science
Replies
6
Views
860
  • Programming and Computer Science
Replies
1
Views
1K
  • Programming and Computer Science
Replies
9
Views
1K
  • Programming and Computer Science
Replies
6
Views
924
Replies
6
Views
1K
  • Programming and Computer Science
3
Replies
81
Views
5K
Back
Top