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>

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 <http://docs.oracle.com/javase/1.5.0/docs/api/java/lang/Number.html Java Math>, <http://docs.oracle.com/javase/1.5.0/docs/api/java/math/BigDecimal.html Java BigDecimal>, and <http://docs.oracle.com/javase/1.5.0/docs/api/java/math/BigInteger.html Java BigInteger>.

The usage of BigDecimal functions add, multiply, and divide may be required.

Java Math:

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
  
  To convert java to string of unlimited length can be achieved via java toString or Matlab char
  
  xstr=toString(xBD)  or xstr=char(xBD)

*Input:* [N,K] [ Inputs to nchoosek(N,K) 0<=K<=N<200 ]

*Output:* C  (char variable of C=nchoosek(n,k) or BigDecimal variable type )

*Theory:*

<http://en.wikipedia.org/wiki/Binomial_coefficient C(n,k)> link shows multiple evaluation methods.

C(n,k)= n!/(k!(n-k)!)

<<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 terms

*Future Challenges:*

1. <http://www.mathworks.com/matlabcentral/cody/problems/1833-usage-of-java-math-add-multiply-pow Usage of java.math>

2. nchoosek_large (full precision)
  3. Next Prime
  4. factor_large

5. <http://www.mathworks.com/matlabcentral/cody/problems/1854-factorial-unlimited-size-java-math Factorial>

Solve

Solution Stats

121 Solutions
46 Solvers

Last Solution submitted on Jan 01, 2023

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 Solvers46

Problem Tags

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 Solvers46

Suggested Problems

More from this Author260

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 Solvers46

Suggested Problems

More from this Author260

Problem Tags

Community Treasure Hunt

Players