Wikipedia:Reference desk/Archives/Mathematics/2013 August 31

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

August 31

Division with small numerator and huge denominator?

If one wishes to divide a small numerator with a huge denominator and accomplish this without being forced to extend the denominator so that one ends up with division of huge numbers which makes calculation slow. How does one accomplish this? I'm thinking of a scenario with a microprocessor like the 6502 that lack any division opcode or FPU. Anyway the key is to "Divide and conquer" so that the division can be executed in small steps, but how? Electron9 (talk) 00:38, 31 August 2013 (UTC)

Sounds like you are using fixed point arithmetic when you should be using floating point. Does that microprocessor not support floating point ? Either this or I'm not understanding the problem. If this is the case, please provide an example which illustrates the problem. StuRat (talk) 02:22, 31 August 2013 (UTC)

The MOS Technology 6502 didn't have built-in floating point. Bubba73 ^{You talkin' to me?} 03:12, 31 August 2013 (UTC)

The 6502 is a primitive 8-bit CPU, so floating point would need to be done in software. For the original question, if the numerator is consistently small and the denominator is consistently big, then it should be possible to scale the denominator, do the division and then unscale the result. For instance, to compute 1.44/1,200,000,000, divide the denominator by a billion, compute 1.44/1.2 = 1.2, then divide the result by a billion = 1.2e-9. To simplify the math, better to divide by a power of 2, here 2^30 would be good, which would just be an arithmetic shift for fixed point numbers. --Mark viking (talk) 03:17, 31 August 2013 (UTC)

Suppose you need to divide 428 / 506829128946. I could then of course divide the denominator as above. But then a lot of the numbers right of the decimal point would be lost. The normal first step would be to ask how many times 506829128946 fit inside 4280000000000 etc. But that ends up with a large division again thus the need to split the task into smaller steps. Electron9 (talk) 07:14, 31 August 2013 (UTC)

Just curious: Why are you trying to use this 38-year-old museum piece ? StuRat (talk) 08:35, 31 August 2013 (UTC)

Because I'm not using it. However it's a good example where one can't away with a built in magic machine instruction(s). It's especially a real situation where low complexity CPU with low power usage is important. Electron9 (talk) 09:26, 31 August 2013 (UTC)

(I think you're missing a few key words in your reply.) I can understand just wanting to know how, as I like knowing how to find square roots, etc. by hand, but what is your real-world situation ? StuRat (talk) 09:54, 31 August 2013 (UTC)

Suitable algoritm to implement division on microcontrollers using assembler etc and to understand it rather than just reusing existing routine. Electron9 (talk) 11:39, 31 August 2013 (UTC)

The 6502 is still used. And it is instructive to know how things like that are done at the low level. Bubba73 ^{You talkin' to me?} 14:39, 31 August 2013 (UTC)

Floating-point arithmetic might help to answer your question. Bubba73 ^{You talkin' to me?} 14:46, 31 August 2013 (UTC)

Division algorithm gives some options. Newton–Raphson division seems a good choice. But first you'll need to choose a number format (like 32 bit significand 8 bit exponent; both with a sign bit), implement the addition, subtraction, multiplication and comparison. Then you perform the division by calculating the inverse of the dividor starting off with a first guess (based on lookup table or just the inverse of the most significant bit of the divider..) Then you repeat X_i+1=X_i(2-d*X_i)

Once you reach a constant value, you multiply that with the numerator. Say you want 5/13: first find 1/13; lets take the inverse of the first digit as guess:

X₀=0.1;

X₁=0.1*(2-13*0.1)=0.07

X₂=0.07*(2-13*0.07)=0.0763

X₃=0.0763*(2-13*0.0763)=0.07691803

X₄=..=0.0769230766

X₅=0.0769230769

X₆=0.0769230769

same value, so you reached max precision (depending on how many bytes you want to use). now multiply with 5, you get 0.3846153846.

You don't have to choose a fixed number format, you can use arrays instead to calculate to any precision you choose. A lot of tedious code copy/pasting if you do that on a 6502 with its eight bit accumulator and two indexregisters, 256 byte stack fixed at page 1... I first learned Z80 assembler on the ZX81, then bought a more powerful Commodore, boy did I miss that extended instruction set and extra registers. Ssscienccce (talk) 13:55, 2 September 2013 (UTC)

Capital omega of Catalan numbers

Hello, I,ve been looking at the number of prime factors with repetition(this as you know uses a capital omega=Ω) of C(n)=(2n)!/[(n+1)(n!)^2]. My reason is basically just for fun exploring, and it's easy to calculate them; it grows very slowly. Anyway, I'm wondering whether Ω(C[n+1])-Ω(C[n]) is unbounded. I bet it is, although so far the biggest jumps have been 2,for example Ω(C[41])-Ω(C(40])=18-16=2.Any information about the growth of Ω(C[n]) (and ω(C[n]), for that matter) would be great too. Thanks.Rich peterson199.33.32.40 (talk) 21:40, 31 August 2013 (UTC)

Boy do I ask silly questions! C(n+1)=[2(2n+1)/(n+2)]C(n), so all I have to do is find n such that 2n+1 is highly composite and that n+2 is much less composite to get big positive jumps, and vice versa to get big negative jumps.-Rich Peterson76.218.104.120 (talk) 04:38, 1 September 2013 (UTC)

For example if n=[3^73-1]/2, then Wolfram MathWorld says n+2 has Ω equal to just 8, while 2n+1=3^73 has Ω=73,so the jump would be Ω(2)+73-8=1+73-8=66....I don't know if it's already known for sure that Ω(2n+1)-Ω(n+2) can be arbitrarily large and also arbitrarily negatively large, but it's probably strongly suspected by number theory people. In any case, I would also be interested very much in information or books dealing with factors of C(n), the Catalan numbers. Thanks again.-Rich76.218.104.120 (talk) 04:52, 1 September 2013 (UTC)