Problem 1855. Usage of java.math : N Choose K with unlimited precision

Created by Richard Zapor

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/image","targetMode":"","relationshipId":"rId1","target":"/media/image1.png"}],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Calculate the binomial coefficient nchoosek with full accuracy. This challenge may use the wonderful word of java.math that allows unlimited precision calculations. The primary reference sites are</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://docs.oracle.com/javase/1.5.0/docs/api/java/lang/Number.html\"><w:r><w:t>Java Math</w:t></w:r></w:hyperlink><w:r><w:t>,</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://docs.oracle.com/javase/1.5.0/docs/api/java/math/BigDecimal.html\"><w:r><w:t>Java BigDecimal</w:t></w:r></w:hyperlink><w:r><w:t>, and</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://docs.oracle.com/javase/1.5.0/docs/api/java/math/BigInteger.html\"><w:r><w:t>Java BigInteger</w:t></w:r></w:hyperlink><w:r><w:t>.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The usage of BigDecimal functions add, multiply, and divide may be required.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Java Math:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[vd-decimal value, vstr-string, vi-integer value \nxBD=java.math.BigDecimal(vd); % valid vd,vstr,vi creates xBD a BigDecimal variable\nimport java.math.*; % simplifies statements\nxBD=BigDecimal(vstr);\nxplusyBD=xBD.add(BigDecimal(y)); % add input requires BD type\nxmultiplyzBD=xBD.multiply(BigDecimal(z)); % multiply input requires BD type\nxdividezBD=xBD.divide(BigDecimal(z)); % divide input requires BD type\nxmultydivz=xBD.multiply(yBD).divide(zBD); out=x*y/z\n\nTo convert java to string of unlimited length can be achieved via java toString or Matlab char\n\nxstr=toString(xBD) or xstr=char(xBD)]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Input:</w:t></w:r><w:r><w:t> [N,K] [ Inputs to nchoosek(N,K) 0&lt;=K&lt;=N&lt;200 ]</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Output:</w:t></w:r><w:r><w:t> C (char variable of C=nchoosek(n,k) or BigDecimal variable type )</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Theory:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:hyperlink w:docLocation=\"http://en.wikipedia.org/wiki/Binomial_coefficient\"><w:r><w:t>C(n,k)</w:t></w:r></w:hyperlink><w:r><w:t> link shows multiple evaluation methods.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>C(n,k)= n!/(k!(n-k)!)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:customXml w:element=\"image\"><w:customXmlPr><w:attr w:name=\"height\" w:val=\"-1\"/><w:attr w:name=\"width\" w:val=\"-1\"/><w:attr w:name=\"relationshipId\" w:val=\"rId1\"/></w:customXmlPr></w:customXml></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The factorial method gives a direct solution while the multiplicative may require fewer operations.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Hint:</w:t></w:r><w:r><w:t> C(5,3)=(5/3)*(4/2)*(3/1)= (5/1)*(4/2)*(3/3); numerator has k terms</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Future Challenges:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>1.</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://www.mathworks.com/matlabcentral/cody/problems/1833-usage-of-java-math-add-multiply-pow\"><w:r><w:t>Usage of java.math</w:t></w:r></w:hyperlink></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[2. nchoosek_large (full precision)\n3. Next Prime\n4. factor_large]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>5.</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://www.mathworks.com/matlabcentral/cody/problems/1854-factorial-unlimited-size-java-math\"><w:r><w:t>Factorial</w:t></w:r></w:hyperlink></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"},{"partUri":"/media/image1.png","contentType":"image/png","content":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAiQAAAA6BAMAAABynl+BAAAAMFBMVEX///9iYmIEBASenp5AQEAwMDCKioq2trYiIiJ0dHQMDAzm5uYWFhZQUFDMzMwAAAAm8IwaAAAAAXRSTlMAQObYZgAACIxJREFUeNrtWmtsVMcVPnv3ce0uXtutCKW08aKoeRWSjairFJritCQ/EkRXalOaWA0kCqWgAAsCpIAqFvEjVaq0C1FABLXZKMqPqE1rU9OkqaLYNJES+lolQQgiipUoEaY1YIMB26y3M2fu3fs6M95ZbygyPtLdvd5v5juzZ2fOnDufASalRbphyrxW31Z9X2NyhqSUnAqJz0aWPjsVEq9t+V1yYgT94q1r8uSrz384sf6Jv4n3WLaqfHW9DNijhPdUzBXqVVCQNLBji/IbXz/ekF63XR6Wk9QtlyExEomzEEY7JLD5wdMWWhHXTwBOnpc5oGgAzjbWKyLC3CR+FfiNZ7i43rVvpjXJc86rsnz1Cb2Y2YxLpCXweqjrFmglXNjwgswBRQOJbMMeRUi4m0Z/9OM3WVwsvTa8Wt66ZlSRrzZQHx54lL0MhiXwv6D0TYFWwnWReTajMgcUDQxmz61ShIS7yfhDOXTU4drmTL0vV5Gv6Lwb5XmpVQLPZQMQaCVc03g6yUsdtOonT+7mSxTQas2SJU68Ps3JWNY/L8u7ipx8TAKzSR1GtCKun/Psk5c5IGjGLW25m9UyPohA7DaWbxoHnjn4Els5REgeOTNzzqz0mpb6iyTA60RxF+xaTBUYbJM79i1IDCNK1JxBrkEekmTn4x+TDggaapiB0nbDk7E3U+70Y7bnBJcBkQfYb9Z/90petJWIPH37B2YmmciN/ZIEINJk3wVteDmHbXLPqOYj6i9+SK67+cpvPzGXdkDQUMP0uzGjvz/nCWXpUsHiMmATa9/6xkzAkHUGGMPt7+XCVL4SAFxos++InbuNw2Vyd4K7B1Gf0VyPsWvfWGY97YCgoYbpcwMjHUdMz/56a7FgcYVgMS9aF/bAjXwhbesMzMJwf5Px8B/OYtsgkG8csO/Y5MMC5yCfpdGtbMGGFnZz2CY/jXN9On/9612IQryPJc83t1s3bi6n8Vk29KdiGZzdQQd4ecqFonN/R4EaHHdT98JSbOG4OdOTFlwR6OQx3Htz4jDf53Z8OxDmz+WgvycfAgkAHWn7Do6s5J//xdOKwRZ5AtHLuF382ob/zK7RXErcuLhcjePsWteS4WmOchBInpufGjnIbxaNbiw4w3T3ZW7Mk08+AZ4x9dn5JhLGIqgPSm9jiIO1M0u5/WnyARyBcymnySz/BCsgbJEP/rYMNOfNYY7C0PfZX/eCdePicjWex1a+MYBLj3CAl6e++MX8++7B8UV2ucfv9OVuMi2nwDumJRYfGCGcZ9+AYoEvrdK/g4txOfwjRK5SBOpy8iahNMI2uVNQb4EYov7UQHKxX3PkJcj+iXZA0HS4tiqKkLvZl74U9+Tl8KF6i8uI8cCEhyHaznfruksBt6kcPPAaFRIBjCbpJjxRRZs4XCYv2+btzW8h6jOaaz8vS4r5Y7QDgma88XM3q+HYmKfWieV2WVwGvsbSMHYjT2BDYwFKtke/v5TyJYBIB9Wk4aFWXu7mOFwmL9sfT5/+KqL+TZjkWsCA1MjOAu2AoBlv/NzNd2Fvgzcr1z9rc23zMv5dtxSM5+XYGiW8pkKu15UOCJplwyLXndUeMnIZSS++QzckQy/KsdlKeHaFXPellBSzoXZDRi6jzXveUOjVdbBJipj7VTCilXCZaRUFRVPtkC2u73k/fT6jyx+WpreoEo5WzHWHygFBM97CkY5JcBnzvJ8WtM9Yiw/LkN1KeHfFXId7FRS7qzhZlY1JcIUOeuvVhbN5bom8g0XdncFei3E37cpebefP7hEve87EWTLQVB3VSd9u34zUX5e17+qCq9LkI9a2gI6ThWvdIr6/Mzt9HzQ6SSokA/7PFlKBmsNkiy3iO/rJ+VfmQEiSSwZCV2su8X5H7WFGfM8m3dnMtZ5LIsd9HxSu8UwS/43hW2qpGoZEKVxqKqNXznYYOSzoy3pgR1BPRCx+iwarxbYiKREu16Iy+p2gConK6FpC0qz9cpWpeEPHjW4sVwezVppNJQONELus84gs2BKnAL4Y2OTXsSjU83LwRN7xatvqOVu7BeoL1fmarw9pGVc00mJUth64gGjEMbNOxyGyqYVLUoWUKKPxHyZrHZKhozLkeCTZgzf7PhUfzCIacayo9Tshm5nDE0Kv3R/dyl4/Yteqlx2vtvXD8GWB+p7mR69cLvmZURQr19ID44uJRhwb0polyKYWLkkVUqaMXknLG5fEoDfEm/leMxojGiE2V4cWe1jC5Veo9ZqyVEjhtWy2MvqZf+/EdPkhiGHgmbytB44NEwcriG3XcCh6qIVLUoWUKaN6lsZlZoIpb4Jypywk0RJ/s/VA6t+ABHaTxphED7VwSaqQMmVUawK0puNHOsB8BsLyCgflTln1OvQ0hnQsAzz7H3iB+M0Re0NnlmCPt9m3zRwBLjO5hEu08xloSJe9utFFdyHqKKP80rLzhwBufgLuXAHRn+6VffF3udwpfRL+pJdvlkIPhC8Q6VBgB3RCgj3GES4dFdKFBpVRVEd1bEw85/WoH/f60orDgX2PQFkPhHaqyEBMpzIQPdTCpUuFdKFBZfTezya/LlEdIZW+BmU9sP6fVJGBWF6nLMEeauGSVCFlymjNDeVOaUgu7oeyHhiaThYZDIu/rFWWcDa1cEmqkDJlNHDSNVFDuVMaEtjl6IE/oo6gBJbVcCh6qIVLUoWUKaOHX/xxR01DIuROqTl7XvyGWrpVC5dayqie/df+Yr3VhYutq/L/xY28UsuQqIVLLWVUz1qsxXGoeooN9qR8vLbP39K1ZvJ5+ZoSrcnqqHqWwE4rnYV/UNvn705p6cCrr/ubVOhEDvOWTDCS/CFso3WWUWMZQilc6imjOramLr6IWRtMWdmSE184k8zqJ3i2EJl8ISn1xeezPPWf7qn1Uk6v11m7RcuDU8Gojf0PBYku0k/USjQAAAAASUVORK5CYII="}]}

Calculate the binomial coefficient nchoosek with full accuracy. This challenge may use the wonderful word of java.math that allows unlimited precision calculations. The primary reference sites are <a href = "http://docs.oracle.com/javase/1.5.0/docs/api/java/lang/Number.html">Java Math</a>, <a href = "http://docs.oracle.com/javase/1.5.0/docs/api/java/math/BigDecimal.html">Java BigDecimal</a>, and <a href = "http://docs.oracle.com/javase/1.5.0/docs/api/java/math/BigInteger.html">Java BigInteger</a>.The usage of BigDecimal functions add, multiply, and divide may be required.Java Math:<pre class="language-matlab">vd-decimal value, vstr-string, vi-integer value 
xBD=java.math.BigDecimal(vd); % valid vd,vstr,vi creates xBD a BigDecimal variable
import java.math.*; % simplifies statements
xBD=BigDecimal(vstr);
xplusyBD=xBD.add(BigDecimal(y)); % add input requires BD type
xmultiplyzBD=xBD.multiply(BigDecimal(z)); % multiply input requires BD type
xdividezBD=xBD.divide(BigDecimal(z)); % divide input requires BD type
xmultydivz=xBD.multiply(yBD).divide(zBD); out=x*y/z
</pre><pre class="language-matlab">To convert java to string of unlimited length can be achieved via java toString or Matlab char
</pre><pre class="language-matlab">xstr=toString(xBD) or xstr=char(xBD) 
</pre>Input: [N,K] [ Inputs to nchoosek(N,K) 0&lt;=K&lt;=N&lt;200 ]Output: C (char variable of C=nchoosek(n,k) or BigDecimal variable type )Theory:<a href = "http://en.wikipedia.org/wiki/Binomial_coefficient">C(n,k)</a> link shows multiple evaluation methods.C(n,k)= n!/(k!(n-k)!)<img src = "http://upload.wikimedia.org/math/b/1/a/b1a5828ee5ec18a1362999a76f3c63e6.png">The factorial method gives a direct solution while the multiplicative may require fewer operations.Hint: C(5,3)=(5/3)*(4/2)*(3/1)= (5/1)*(4/2)*(3/3); numerator has k termsFuture Challenges:1. <a href = "http://www.mathworks.com/matlabcentral/cody/problems/1833-usage-of-java-math-add-multiply-pow">Usage of java.math</a><pre class="language-matlab">2. nchoosek_large (full precision)
3. Next Prime
4. factor_large
</pre>5. <a href = "http://www.mathworks.com/matlabcentral/cody/problems/1854-factorial-unlimited-size-java-math">Factorial</a>

Solve

Solution Stats

71 Solutions
21 Solvers

Last Solution submitted on Sep 04, 2020

Last 200 Solutions

Problem Comments

Solution Comments

Solution 335235

1 Comment

1 Comment

James on 17 Oct 2013

I forgot to check nchoosekJava(1,1) :-(

Problem Recent Solvers21

Problem Tags

bigdecimal java nchoosek

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 1855. Usage of java.math : N Choose K with unlimited precision

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers21

Suggested Problems

More from this Author246

Problem Tags

Community Treasure Hunt

Problem 1855. Usage of java.math : N Choose K with unlimited precision

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers21

Suggested Problems

More from this Author246

Problem Tags

Community Treasure Hunt

Players