5 Replies - 2805 Views - Last Post: 14 February 2013 - 05:52 PM

#1 NecroWinter  Icon User is offline

  • D.I.C Regular

Reputation: 36
  • View blog
  • Posts: 320
  • Joined: 21-October 11

nth digit of decimal expansion

Posted 13 February 2013 - 06:58 PM

hey there quick question, I'm not finding good results on google, as most examples tend to be made for humans and not algorithms

Basically, i'm going to take two integers, divide them, and then find the nth digit to the right of the "."

So for example, if I divide 5/156, the answer (it repeats, so this is not perfect) is: .0320512820512820512820512820512820512820512820512820

if I want to find the second digit, its 3
if I want to find the fourth digit, its 0
Fifth: 5
Sixth: 1
etc

I cant simply do division here, because any data type will truncate the value. So I need to create a loop and do a process over and over. I know it has something to do with mod, but im not sure what.

Unfortunately, its very difficult for me to present code for someone to analyze for a mathematical process that I dont understand, so im hoping someone can help me figure out a formula that I can loop over to just keep finding arbitrary digits in a decimal expansion.

This post has been edited by NecroWinter: 13 February 2013 - 07:02 PM


Is This A Good Question/Topic? 0
  • +

Replies To: nth digit of decimal expansion

#2 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2112
  • View blog
  • Posts: 3,230
  • Joined: 21-June 11

Re: nth digit of decimal expansion

Posted 13 February 2013 - 07:06 PM

Do you know long division? If you had to calculate 5/156 using only pen and paper, which steps would you follow?
Was This Post Helpful? 2
  • +
  • -

#3 lordofduct  Icon User is offline

  • I'm a cheeseburger
  • member icon


Reputation: 2533
  • View blog
  • Posts: 4,633
  • Joined: 24-September 10

Re: nth digit of decimal expansion

Posted 13 February 2013 - 08:58 PM

sepp2k is giving you a good hint

when you do long division, you divide, find the remainder, expand the remainder (usually by sticking the next digit on, or 0 if no digit is there), and cotinue dividing and finding the remainder again.

modulo gives you the remainder

What is adding 0 to then end though? You're just basically multiplying by 10...

divide, get remainder, expand, divide, get remainder, expand, divide, get remainder, expand

we have a looping algorithm!

(note the divide part is really only important for the digit you want to find, the last step in the loop... as the divide is the act of finding that digit at that position)

This post has been edited by lordofduct: 13 February 2013 - 09:27 PM

Was This Post Helpful? 2
  • +
  • -

#4 NecroWinter  Icon User is offline

  • D.I.C Regular

Reputation: 36
  • View blog
  • Posts: 320
  • Joined: 21-October 11

Re: nth digit of decimal expansion

Posted 14 February 2013 - 10:45 AM

I got it shortly after sepp posted.

the algorithm I came to was:


 int tmp=0;
   
    for (int i=0;i<count;i++) 
        {
		numerator = numerator*10;
		tmp = numerator/denominator;
		numerator = numerator%denominator;
		
         }

    return  tmp;


This post has been edited by NecroWinter: 14 February 2013 - 10:47 AM

Was This Post Helpful? 0
  • +
  • -

#5 lordofduct  Icon User is offline

  • I'm a cheeseburger
  • member icon


Reputation: 2533
  • View blog
  • Posts: 4,633
  • Joined: 24-September 10

Re: nth digit of decimal expansion

Posted 14 February 2013 - 03:13 PM

if you want, check this algorithm out (it's the one I wrote last night while drunk and responding to this post). It's in C#:

public static int GetNthDigit(double n, double d, int digit)
{
	for(int i = 0; i < digit; i++)
	{
	    n = (n % d) * 10;
	}
	
	return Math.Floor(n / d);
}



note I don't do any dividing until the end, as we don't really need to do that part

this works with none integers as well

This post has been edited by lordofduct: 14 February 2013 - 03:17 PM

Was This Post Helpful? 2
  • +
  • -

#6 NecroWinter  Icon User is offline

  • D.I.C Regular

Reputation: 36
  • View blog
  • Posts: 320
  • Joined: 21-October 11

Re: nth digit of decimal expansion

Posted 14 February 2013 - 05:52 PM

this weekend im gonna try that algorithm in lisp :P

I did the other algorithm in Java though, I definitely like me some imperative programming
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1