14 Replies - 2624 Views - Last Post: 18 February 2012 - 07:36 AM Rate Topic: -----

#1 Itchigon  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 31
  • Joined: 17-February 12

Getting the nth integer from a double

Posted 17 February 2012 - 06:07 AM

Hi,

I have an assignment (so please don't give me code just an explanation/helpful hints). Basically I divide two integers that are input by the user (e.g. 8 & 13) and store the result in a double. So if I were to do 8/13 I would get 0.615384615384615384615384...

The user also enters another number n. This is the number they want after the decimal place. With the example above if the user entered 8 13 5 then they would get the digit 8 as it is the 5th digit after the decimal point.

I tried converting to a string using sprintf and searching through it from the position where the decimal point is and it works but it doesn't work for large numbers (i.e. 8 13 60000). So I am trying another way where I am trying to multiply out the decimal point from the double. However I am unsure how to go about doing this.

#include <stdio.h>
#include <math.h>

main()
{

	int a; //First number to divide
	int b; //Second number to divide
	int n; //Number after decimal point to print
	int i; 
	double divAnswer = 0;
	double fractional;
	double integer;

	scanf("%d %d %d", &a, &b, &n);

	divAnswer = (double)a/(double)b;

	fractional = modf(divAnswer, &integer);

	printf("%f", fractional);	

	printf("\n%lf", pow(fractional, n));
}



As you can see I am trying to use pow but i'm not sure how to go about doing it. Any help would be appreciated.

Is This A Good Question/Topic? 0
  • +

Replies To: Getting the nth integer from a double

#2 CTphpnwb  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 3100
  • View blog
  • Posts: 10,889
  • Joined: 08-August 08

Re: Getting the nth integer from a double

Posted 17 February 2012 - 06:58 AM

Multiply the double by 10^n and then take the modulus of that number vs 10 to get the digit.
Was This Post Helpful? 1
  • +
  • -

#3 Karel-Lodewijk  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 451
  • View blog
  • Posts: 855
  • Joined: 17-March 11

Re: Getting the nth integer from a double

Posted 17 February 2012 - 07:03 AM

Your multiplying out technique seems certainly viable. I would say, keep multiplying the number by 10 and until it is >= 0.1.

As for digits far away, it is very much possible that your double does not have any information about that. Numbers when stored in a double have a limited precision, so if they have an infinite representation like 1/3 or pi or something then they are rounded at some point. I can guarantee that you won't find the 60000th digit of 8/13 by examining a double.

Anyway, there is also a more mathematical approach. Basically the division itself generates a lot of information you don't need. What you could do is this:

nth dec. digit of x/y
= n-1th dec. digit of x*10/y
= n-2th dec. digit of x*10^2/y
...
= 1st dec. digit of x*10^(n-1)/y

Now we only need the first digit, so we aren't really interested in an exact result, as long as the first digit is preserved. We can accomplish this by doing what is called a modular exponential.

1st digit of x*10^(n-1)/y
= 1st digit of (x*10^(n-1) mod y) / y

Note that x*10^(n-1)/y is not equal to (x*10^(n-1) mod y) / y, but it does preserve the first decimal digit. Everything bigger than the decimal digit will be rubbish though.

There are efficient algorithms that calculate a modular exponential (10^n-1 mod y) in your case without ever calculating a 10^(n-1), I've written one once:

Spoiler


With this algorithm you will be able to find the 60000th digit of some division.

P.S.: I tried it, the 60000th decimal digit of 8/13 is a 4 ;)

This post has been edited by Karel-Lodewijk: 17 February 2012 - 03:46 PM

Was This Post Helpful? 2
  • +
  • -

#4 Itchigon  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 31
  • Joined: 17-February 12

Re: Getting the nth integer from a double

Posted 17 February 2012 - 07:31 AM

Thanks for your input guys.

Karel: I'm not quite sure I understand what you are saying as i'm not the best at maths. Is there any chance you could give me some pseudocode for this section that you were talking about?

Quote

nth dec. digit of x/y
= n-1th dec. digit of x*10/y
= n-2th dec. digit of x*10^2/y
...
= 1st dec. digit of x*10^(n-1)/y

Was This Post Helpful? 0
  • +
  • -

#5 Karel-Lodewijk  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 451
  • View blog
  • Posts: 855
  • Joined: 17-March 11

Re: Getting the nth integer from a double

Posted 17 February 2012 - 07:53 AM

View PostItchigon, on 17 February 2012 - 02:31 PM, said:

Thanks for your input guys.

Karel: I'm not quite sure I understand what you are saying as i'm not the best at maths. Is there any chance you could give me some pseudocode for this section that you were talking about?

Quote

nth dec. digit of x/y
= n-1th dec. digit of x*10/y
= n-2th dec. digit of x*10^2/y
...
= 1st dec. digit of x*10^(n-1)/y


That part was not meant to be coded, it's just part of the derivation. What you should code is simply this:

x * (10^n-1 mod y) / y



The 1st decimal digit of this expression will be the same as the nth decimal digit of x/y.

But (10^n-1 mod y) is somewhat problematic if you code it naively i.e.:pow(10,n-1) % y. Calculating 10^n-1 will get you a number that is very large and will overflow a variable quite quickly, while (10^n-1 mod y) will never get very large (<y). My snippet of code calculates that part efficiently without overflowing and in in O(log(n)) time, it's based on http://en.wikipedia....t_binary_method .

This post has been edited by Karel-Lodewijk: 17 February 2012 - 07:58 AM

Was This Post Helpful? 1
  • +
  • -

#6 Itchigon  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 31
  • Joined: 17-February 12

Re: Getting the nth integer from a double

Posted 17 February 2012 - 09:28 AM

Ok, my code is now as follows:

#include <stdio.h>
#include <math.h>

long modular_pow(long base, long exponent, long modulus) {
    long result = 1;
    while (exponent > 0) {
        if ((exponent & 1) == 1)
           result = (result * base) % modulus;
        
        exponent = exponent >> 1;
        base = (base * base) % modulus;
    }
    return result;
}


main()
{
	int a, b, n; //Two integers to divide and nth digit to get.
	int temp;
	double dividedNum; //A and B divided

	scanf("%d %d %d", &a, &b, &n);

	dividedNum = (double)a/(double)b;

	 
}



I am unsure how I am meant to call the function you wrote Karel. Do I just pass it a, b and n and it will return the result? e.g.

result = modular_pow(a, b, n);


Was This Post Helpful? 0
  • +
  • -

#7 Karel-Lodewijk  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 451
  • View blog
  • Posts: 855
  • Joined: 17-March 11

Re: Getting the nth integer from a double

Posted 17 February 2012 - 02:29 PM

View PostItchigon, on 17 February 2012 - 04:28 PM, said:

I am unsure how I am meant to call the function you wrote Karel. Do I just pass it a, b and n and it will return the result? e.g.


The function I wrote is not a solution to your program it's just calculates: base^exponent mod modulus. Since I've written the solution it I might as well post it, but you made it clear you didn't want any code.

Spoiler

This post has been edited by Karel-Lodewijk: 17 February 2012 - 02:31 PM

Was This Post Helpful? 1
  • +
  • -

#8 CTphpnwb  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 3100
  • View blog
  • Posts: 10,889
  • Joined: 08-August 08

Re: Getting the nth integer from a double

Posted 17 February 2012 - 03:12 PM

Seems a bit complicated.
Spoiler

This post has been edited by CTphpnwb: 17 February 2012 - 03:15 PM

Was This Post Helpful? 1
  • +
  • -

#9 r.stiltskin  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1833
  • View blog
  • Posts: 4,927
  • Joined: 27-December 05

Re: Getting the nth integer from a double

Posted 17 February 2012 - 03:25 PM

View PostCTphpnwb, on 17 February 2012 - 05:12 PM, said:

Seems a bit complicated.

Not really. The OP wants to be able to find the 60000th digit of a repeating fraction. Your solution can't do that because it works only as far as the precision of the double. Karel-Lodewijk's method isn't subject to that limitation.
Was This Post Helpful? 1
  • +
  • -

#10 Itchigon  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 31
  • Joined: 17-February 12

Re: Getting the nth integer from a double

Posted 17 February 2012 - 03:29 PM

View PostCTphpnwb, on 17 February 2012 - 03:12 PM, said:

Seems a bit complicated.
Spoiler


This works for small n (e.g. n = 5) but it doesn't work for n upto 60000. e.g. I entered 8 13 60000 and got -8 back.

Also, i'm using C not C++ and having a problem adapting the code by Karel. I have to take input of two numbers and the nth digit i want to look at, i.e. 8 13 5 = a b n.
Was This Post Helpful? 0
  • +
  • -

#11 Karel-Lodewijk  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 451
  • View blog
  • Posts: 855
  • Joined: 17-March 11

Re: Getting the nth integer from a double

Posted 17 February 2012 - 03:40 PM

Besides the input/output, I'm using nothing c++ specific. Just include math.h instead of cmath and write io with printf/scanf.
Was This Post Helpful? 1
  • +
  • -

#12 Itchigon  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 31
  • Joined: 17-February 12

Re: Getting the nth integer from a double

Posted 17 February 2012 - 03:50 PM

View PostKarel-Lodewijk, on 17 February 2012 - 03:40 PM, said:

Besides the input/output, I'm using nothing c++ specific. Just include math.h instead of cmath and write io with printf/scanf.


I keep getting the error: In function nthdigit: error: expected expression before 'int'

Here's the code:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

long modular_pow(long base, long exponent, long modulus) {
    long result = 1;
    while (exponent > 0) {
        if ((exponent & 1) == 1)
           result = (result * base) % modulus;      
        exponent = exponent >> 1;
        base = (base * base) % modulus;
    }
    return result;
}

int nthdigit(double x, double y, long n) {
    double temp = (x * modular_pow(10, n-1, y) / y); //this is the formula

    return int(10 * temp) % 10; //extracts 1st decimal digit
}

int main() {

	double x;
	double y;
	long n;

	scanf("%f %f %ld", &x, &y, &n);

	printf("%d", nthdigit(x, y, n));
}




I can't see what is wrong with it.
Was This Post Helpful? 0
  • +
  • -

#13 Karel-Lodewijk  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 451
  • View blog
  • Posts: 855
  • Joined: 17-March 11

Re: Getting the nth integer from a double

Posted 17 February 2012 - 03:55 PM

scanf("%lf %lf %ld", &x, &y, &n);



Apart from that gcc can't find any errors and it works fine here.
Was This Post Helpful? 1
  • +
  • -

#14 Itchigon  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 31
  • Joined: 17-February 12

Re: Getting the nth integer from a double

Posted 17 February 2012 - 04:02 PM

View PostKarel-Lodewijk, on 17 February 2012 - 03:55 PM, said:

scanf("%lf %lf %ld", &x, &y, &n);



Apart from that gcc can't find any errors and it works fine here.


Fixed, it was type-casting using C++ style, C style is (int)....

Works perfectly and submits fine. Thanks alot for your help I couldn't have done it at all without your help.

Thanks to everyone else also for their input, very useful.
Was This Post Helpful? 0
  • +
  • -

#15 Karel-Lodewijk  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 451
  • View blog
  • Posts: 855
  • Joined: 17-March 11

Re: Getting the nth integer from a double

Posted 18 February 2012 - 07:36 AM

You asked me in a pm how this method works:

long modular_pow(long base, long exponent, long modulus) {
    long result = 1;
    while (exponent > 0) {
        if ((exponent & 1) == 1)
           result = (result * base) % modulus;      
        exponent = exponent >> 1;
        base = (base * base) % modulus;
    }
    return result;
}



First of all, understand that it does nothing more than:

long modular_pow(long base, long exponent, long modulus) {
    return pow(base, exponent) % modulus;
}



The problem is that pow(base, exponent) overflows a variable quite quickly, even an unsigned long has a maximum value of 1.84467441 × 10^19 (2^64). So with base 10 as we use it in the code, this would overflow a long with n as low as 20. The result however will never be larger than modulus. The first solution that would come to mind is.

long modular_pow(long base, long exponent, long modulus) {
    long result = 1;
    for (long i = 1; i < exponent; ++i)
        result = (result * base) % modulus;
    return result;
}



Note that each time we multiply by base, we the modulus immediately, we never get a intermediate result much larger than modulus (always smaller than base * modulus). This will not overflow quite so fast.

Now the actual code I wrote is an improvement on that. Because numbers are stored as a binary number in memory, 2 operations are very cheap. *2 and /2, because we can write them by shifting all bytes left or right respectively. Think about how multiplying by 10 is very easy for decimal numbers, 50*10, is just putting a 0 before the 50 (shift left), 50/10 is just removing a 0 (shift right). Basically this last function exploits this by rewriting the exponent in a part that is a power of 2 and a part that is not. The exact method is described here: http://en.wikipedia....t_binary_method .

This post has been edited by Karel-Lodewijk: 22 March 2012 - 07:57 AM

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1