Won't we require to check recurring till at-least two complete iterations of recurrence pattern. Also what's the division logic are we going to use ?
In all modern day processor systems, we are likely to have a math co/sub-processor which will efficiently crunch numbers and round them off to our desire. Another way to look at this problem is by considering the no as sequence of digit and can apply any substring algorithm to find recurrence with better efficiency. My 2 Paise. :) On Sat, Jun 12, 2010 at 8:07 PM, Anurag Sharma <anuragvic...@gmail.com>wrote: > Since we are given numerator 'n' and denominator 'd' separately already. > and considering n and d as integers and d!=0 we can safely assume n/d as > either a terminating fraction or a non terminating but recurring fraction, > in which case we have to find the recurring digits of the fraction. > > Now what I suggested was almost same as Ravi's approach. > take a Set 'S' keeping tuples (R,Q) where R is the current remainder and Q > is the factor such that d*Q is subtracted from the number to get R. > In other words. if at an intermediate step of division we have 'a' as the > divident left then Q=floor(a/d) and R=a%d > > Keep dividing 'n' by 'd' like it is done manually. After every division > check- > 1. If the current remainder is not present in 'S' then add current > remainder 'R' and corresponding quotient 'Q' in the set > 2. If R is found in the set S, then all the following entries in the set > until end will constitute the recurring digits. > taking Ravi's example:- > > Example: > 7) 9 (1.*285714*28 S=[] > 7 > -- > 20 S=[(2,2)] > 14 > --- > 60 S=[(2,2), (6,8)] > 56 > --- > 40 S=[(2,2), (6,8), > (4,5)] > 35 > --- > 50 S=[(2,2), (6,8), > (4,5), (5,7)] > 49 > --- > 10 S=[(2,2), (6,8), > (4,5), (5,7), (1,1)] > 7 > ---- > 30 S=[(2,2), (6,8), > (4,5), (5,7), (1,1), (3,4)] > 28 ^ > ---- | > 20 2 is found in S here, > so recurring digits are "285714" > 14 > > ---- > 60 > 56 > repeats > > > hope its clear > > > Anurag Sharma > > > > On Sat, Jun 12, 2010 at 4:02 PM, divya jain <sweetdivya....@gmail.com>wrote: > >> @anurag >> >> i dint get ur approach..which numerator n denominator u r talking >> about..plz explain.. thanks in advance >> >> On 11 June 2010 08:57, Anurag Sharma <anuragvic...@gmail.com> wrote: >> >>> Please note that the fractional repeating part is recurring. and so that >>> 4th temporary variable assignment will be this way-> >>> temp=x*10000 - x= 233456.34563456... - 23.34563456.... = 233433.0 ( >>> mark the fractional part is 0 now since the infinitely repeating 3456... >>> will get cancelled) >>> In this case you can say that 4 places are repeating. But yes its >>> according to the maths and in any programming language whenever you divide >>> the numerator and denominator you wont get this infinitely recurring decimal >>> places. >>> >>> @divya, also your approach wont work if the recurring fractional digits >>> start after few places from the decimal like in the case of >>> 23.123345634563456.... (note here after the decimal place 123 is not >>> repeating while 3456.. after this 123 is repeating.) >>> >>> What I suggest in this case is keep dividing the numerator by denominator >>> and at every step keep inserting the tupple (remainder, quotient) of that >>> division step in a set. and before inserting in the set check whether it >>> already exists. If yes then the all the quotients following from that point >>> (including the point) will be recurring. >>> >>> Regards, >>> >>> Anurag Sharma >>> >>> >>> >>> On Thu, Jun 10, 2010 at 8:25 AM, Veer Sharma >>> <thisisv...@rediffmail.com>wrote: >>> >>>> Seems it wont work... >>>> x=23.34563456 >>>> >>>> temp = x*100 -x = 233.4563456 - 23.34563456 = 210.11071104 >>>> temp = x*100 -x = 2334.563456 - 23.34563456 = 2311.21782144 >>>> temp = x*1000 -x = 23345.63456 - 23.34563456 = 23322.28892544 >>>> temp = x*10000 -x = 233456.3456 - 23.34563456 = 233432.99996544 >>>> temp = x*100000 -x = 2334563.456 - 23.34563456 = 2334540.11036544 >>>> >>>> ... >>>> >>>> On Jun 9, 11:24 pm, Anurag Sharma <anuragvic...@gmail.com> wrote: >>>> > multiply the original number x=23.34563456 >>>> > >>>> > Anurag Sharma >>>> > >>>> > On Wed, Jun 9, 2010 at 10:36 PM, Veer Sharma < >>>> thisisv...@rediffmail.com>wrote: >>>> > >>>> > >>>> > >>>> > > One question: >>>> > >>>> > > No x = 23.34563456 >>>> > > temp = x X 10 = 233.4563456 >>>> > > temp = temp - x = 210.11071104 >>>> > > decimal part zero? No. >>>> > > Now multiply the no. with 100. Which no? original x (= 23.34563456) >>>> or >>>> > > new no. temp (=210.11071104)? >>>> > >>>> > > On Jun 9, 8:12 pm, divya jain <sweetdivya....@gmail.com> wrote: >>>> > > > multiply the no. with 10 nd store in temp. now subtract no from >>>> temp. >>>> > > check >>>> > > > if the decimal part is zero if yes. then 1st digit after decimal >>>> is >>>> > > > recurring. if no. multiply the no with 100 and repeat . if this >>>> time >>>> > > decimal >>>> > > > part is zero then 2 digits after decimal r recurring nd so on.. >>>> > >>>> > > > On 8 June 2010 21:45, Veer Sharma <thisisv...@rediffmail.com> >>>> wrote: >>>> > >>>> > > > > You have a Numerator and Denominator. After division you might >>>> get a >>>> > > > > recurring decimal points float as the answer. >>>> > >>>> > > > > Problem is: You need to identify the recurring part for a given >>>> > > > > decimal no? >>>> > > > > For example 23.34563456 ... >>>> > > > > return 3456 >>>> > >>>> > > > > -- >>>> > > > > You received this message because you are subscribed to the >>>> Google >>>> > > Groups >>>> > > > > "Algorithm Geeks" group. >>>> > > > > To post to this group, send email to algogeeks@googlegroups.com >>>> . >>>> > > > > To unsubscribe from this group, send email to >>>> > > > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >>>> <algogeeks%2bunsubscr...@googlegroups.com> >>>> > > <algogeeks%2bunsubscr...@googlegroups.com> >>>> > > > > . >>>> > > > > For more options, visit this group at >>>> > > > >http://groups.google.com/group/algogeeks?hl=en.-Hide quoted text >>>> - >>>> > >>>> > > > - Show quoted text - >>>> > >>>> > > -- >>>> > > You received this message because you are subscribed to the Google >>>> Groups >>>> > > "Algorithm Geeks" group. >>>> > > To post to this group, send email to algoge...@googlegroups.com. >>>> > > To unsubscribe from this group, send email to >>>> > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >>>> <algogeeks%2bunsubscr...@googlegroups.com> >>>> > > . >>>> > > For more options, visit this group at >>>> > >http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - >>>> > >>>> > - Show quoted text - >>>> >>>> -- >>>> You received this message because you are subscribed to the Google >>>> Groups "Algorithm Geeks" group. >>>> To post to this group, send email to algoge...@googlegroups.com. >>>> To unsubscribe from this group, send email to >>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >>>> . >>>> For more options, visit this group at >>>> http://groups.google.com/group/algogeeks?hl=en. >>>> >>>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to algoge...@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >>> . >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
