Wikipedia:Reference desk/Archives/Mathematics/2006 October 4

Humanities Science Mathematics Computing/IT Language Miscellaneous 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 at one of the pages linked to above.

about group

if |x|=40, what are the elements of <x> that have order 10.

Please take a moment to review with the instructions at the top of the page. We're pleased to help out with most questions, but I'm afraid that we have to ask you to Do your own homework. If you need help with a specific part or concept of your homework, feel free to ask, but please do not post entire homework questions and expect us to give you the answers. ☢ Ҡi∊ff⌇↯ 08:55, 4 October 2006 (UTC)

You'll find an answer in cyclic group.--gwaihir 09:57, 4 October 2006 (UTC)

subgroup

if G is a group that has exactly eight elements of order 3. how many subgroups of order 3 does G have?

Please take a moment to review with the instructions at the top of the page. We're pleased to help out with most questions, but I'm afraid that we have to ask you to Do your own homework. If you need help with a specific part or concept of your homework, feel free to ask, but please do not post entire homework questions and expect us to give you the answers. ☢ Ҡi∊ff⌇↯ 08:55, 4 October 2006 (UTC)

Hint: How many elements can two subgroups of order 3 have in common?--gwaihir 09:55, 4 October 2006 (UTC)

Fast

Which is the fastest way to 1)add 2 numbers 2)subtract 2 numbers 3)multiply 2 numbers 4)divide 2 numbers 5)find power of any number 6)find factorial of any number

You need to give some more context in your question. Any meaningful answer depends at least on

1. How big the numbers are.
2. How much precision you want in your answers.
3. What mechanical or electronic aids you can use - pencil and paper ? abacus ? pocket calculator ? supercompter ?

and maybe on other factors as well. Gandalf61

the numbers are 1000 to 1000000 digits long we want exact answer with max precision possible using a normal computer and programming languages

See the articles on arbitrary-precision arithmetic and computational complexity of mathematical operations. Gandalf61 13:08, 4 October 2006 (UTC)

Two good references are Donald Knuth's The Art of Computer Programming and Prime Numbers - A Computational Perspective by Richard Crandall and Carl Pomerance. From a more practical perspective, you may be interested in studying (or making direct use of) some existing library for high-precision arithmetic such as the GNU Multi-Precision Library. Some of these libraries have good documentation of algorithms on their websites. Fredrik Johansson 14:04, 4 October 2006 (UTC)

(edit conflict) I would like to point to GMP for integers and rational numbers and MPFR for floating-point numbers. Both are free (LGPL license) and fast. The former come with C and C++ interfaces and the latter has a C interface (but I think others have created interfaces for other languages as well). —Bromskloss 14:16, 4 October 2006 (UTC)

With integer powers, you can use a recursive method that minimizes multiplication by splitting the power in two (rounding down, and multiplying by the number if it's rounded):

$6^{18}=(6^{9})*(6^{9})$

$6^{9}=(6^{4})*(6^{4})*6$

$6^{4}=(6^{2})*(6^{2})$

$6^{2}=6*6$

So the calculation ends up doing 5 multiplications, and at each step there are a few integer divide-by-twos (you can do this with a right shift) and probably two comparisons about whether to continue and whether to add the uneven multiply in there.

With factorials, you can store a bunch in a table, they tend not to be very useful as the number gets large anyway. There's also a "gamma function" which gives you an integral that you could solve (though you'd end up having to calculate some power of e), possibly. - Rainwarrior 20:11, 4 October 2006 (UTC)

Oh, I didn't notice you had mentioned that you actually are using gigantic numbers too.. yeah, a table of factorials wouldn't be that useful then (unless you only need the low factorials most of the time). Anyhow, the advice to use GMP is sound, these things work well and these problems have already been worked on by the people who made them. Also, in Java there are classes called BigDecimal and BigInteger that handle large numbers, though if efficiency is very important you'll probably want to use C++, or maybe Fortran. - Rainwarrior 20:18, 4 October 2006 (UTC)

Is there any place where I can get detailed explanations of using these all algorithms in c/c++/c#/java/j#

(Please sign your comments.) I'm not sure I understand what you mean. GMP and MPFR are libraries that you download and use in your program, so have a look at the homepage of the one you want. You can probably get instructions of how to use them there. —Bromskloss 11:47, 5 October 2006 (UTC)

There's no way you can have all digits of the factorial of an 1000 digit number though. – b_jonas 18:45, 5 October 2006 (UTC)

Can't speak for other languages, but java.math.BigInteger should pretty much be able to do all of that without much problem (well, except for the factorial, that's just ridiculous). It's probably better to use code that someone else that knows what he's doing has written, because these algorithms can be very tricky. Why reinvent the wheel? However, if you want to program these yourself, you should probably go with The Art of Computer Programming vol. 2, Seminumerical Algorithms. It's fantastic. Oskar 23:22, 5 October 2006 (UTC) (PS: I actually did a big-number program for my TI-83+ back in the day from TAoCP that used a residue number system. I was so proud of myself ;)

What is a seminumerical algorithm? —Bromskloss 07:23, 6 October 2006 (UTC)

Seminumerical algorithms, meaning algorithms that have to do with numbers, is the second volume of The Art of Computer Programming, possibly a series of greatest books on programming ever written. They are very dense and techincal, yet still fairly readable if you know what you are doing. Oskar 16:35, 7 October 2006 (UTC)

(it's called seminumerical, because many of the algorithms in the book are borderline between numerical and symbolical algorithms. for instance, he describes how to make an algorithm to factor a polynomial, which is arguably a symbolic algorithm Oskar 16:39, 7 October 2006 (UTC))

where can i get an ebook of The Art of Computer Programming--Utkarshkukreti 05:26, 7 October 2006 (UTC)

You can't, you need to buy it. Go to a bookstore and look through it and see if you are really up to the challenge, because it is a difficult book. Then, if you can afford it and are up to the challenge, by all means, buy it. Oskar 16:35, 7 October 2006 (UTC)

Or borrow it from a library. That's cheaper, and, for example, the Hungarian translation is sold out completely so that's the only thing you can do. – b_jonas 12:16, 8 October 2006 (UTC)