현재 위치

홈 ›› Forums ›› 공부 ›› 프로그래밍 QnA

매우 큰 정수끼리의 나누기?

Seven..의 이미지
글쓴이: Seven.. / 작성시간: 토, 2004/06/12 - 9:25오전

10진수로
한 50자리정수에서 20자리 정수를 나눠야 하는데
이게.. 만만치가 않네요 -_-

어떤 좋은 방법이 있을까요?;;;
나누기가 떨어지는지 아닌지만 판별해도 되거든요....^^

File attachments: 
첨부파일 크기
Package icon vnl_bignum_demo.zip100.98 KB
Forums: 
프로그래밍 QnA
차리서의 이미지

글쓴이: 차리서 / 작성시간: 토, 2004/06/12 - 10:06오전

한 번만 확인해보시려는거면 bc를 쓰시거나, 혹은 프로그램 내에서의 문제라면 GNU MP 라이브러리의 정수 나눗셈 함수들을 쓸 수 있습니다.

--
자본주의, 자유민주주의 사회에서는 결국 자유마저 돈으로 사야하나보다.
사줄테니 제발 팔기나 해다오. 아직 내가 "사겠다"고 말하는 동안에 말이다!

taeyeung의 이미지

글쓴이: taeyeung / 작성시간: 토, 2004/06/12 - 10:21오전

openssl의 BIG_NUM 관련 라이브러리를 사용해 보세요

큰 정수를 다루는 여러 함수와 구조체를 제공합니다.

hjlee의 이미지

글쓴이: hjlee / 작성시간: 토, 2004/06/12 - 10:22오전

Ruby, Python, CMU Lisp 에서 나머지 구하는 것입니다.

$ irb
irb(main):001:0> 3298433280483209483208402384092834028340823094820384023840238402384098230432 % 3212038901283080182309128328210328123321231231
=> 1128685941812964633381803964244290876440336237
irb(main):002:0> 
$ python
Python 2.3.4 (#2, May 29 2004, 03:31:27)
[GCC 3.3.3 (Debian 20040417)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> 9312823038201983128301823098120381209830128309218230109321803909123830981092380183013238210398 % 2310821930380912830981209380183091283012331231
532205282735077454127723470974423873448117028L
>>>
$ lisp
CMU Common Lisp CVS release-18e-branch + minimal debian patches, running on hjnotebook
With core: /usr/lib/cmucl/lisp.core
Dumped on: Fri, 2004-06-04 09:10:33+09:00 on hjnotebook
For support see http://www.cons.org/cmucl/support.html Send bug reports to the debian BTS.
or to pvaneynd@debian.org
type (help) for help, (quit) to exit, and (demo) to see the demos

Loaded subsystems:
    Python 1.1, target Intel x86
    CLOS 18e (based on PCL September 16 92 PCL (f))
* (mod 348093284023840283402332423482309840238409283094820384023840233294802384023890433024 8234094238403284028340283402390482304832)

1854366119782816955825952402026414641344
* (quit)

http://hj-lee.github.io/

hjlee의 이미지

글쓴이: hjlee / 작성시간: 토, 2004/06/12 - 10:27오전

가장 기본적인 bc 를 잊었군요.

c++ 에서 GNU MP 사용 예 -

#include <gmpxx.h>
#include <iostream>

int main() 
{
	mpz_class a, b, q, r;

	a = "321812390810238012840812402801280921830921311233123123124354356998908432343289482384028409283409824802934802394823433";
	b = "9438943894893484394889348342379347342987433";
	q = a / b;
	r = a % b;
	std::cout << "q = " << q << "\tr = " << r << std::endl;
	return 0;
}

결과는

$ a.out
q = 34094109933669604420411304962576325183921782470517622332372524590974983869 r = 5319886669181353700100333211296574950105156

java 에는 java.math.BigInteger

http://hj-lee.github.io/

datamind의 이미지

글쓴이: datamind / 작성시간: 토, 2004/06/12 - 10:37오전

잠깜 생각해보았는데,

정수를 배열로 저장한다음에,
x / y = z + a
=> x = z * y + a 에서,
x 와 z * y 의 자리수를 먼저 같게 한후,
y 를 바꾸면서 값을 구함.

예1)

9876543210 / 654321 = z + a
=> 9876543210 = z * 654321 + a
=> 9876543210 은 10자리
654321 는 6자리
그러므로, z 는 10000 이 초기 값,
=> 9876543210 > (654321 * 10000 = 6543210000) 이므로,
9876543210 < (654321 * 20000 = 13086420000) 이므로,
z 의 첫번째 수는 1 임을 알수 있고,
9876543210 > (654321 * 11000 = 7197531000)
...
9876543210 > (654321 * 15000 = 9814815000)
9876543210 < (654321 * 16000 = 10469136000) 이므로,
z 의 두번째 수는 5임을 알수 있고,
9876543210 < (654321 * 15100 = 9880247100) 이므로,
z 의 세번째 수는 0 임을 알수 있고,
9876543210 > (654321 * 15010 = 9821358210)
...
...

예2)
9876543210 - (654321*10000) = 3333333210
3333333210 - (654321*10000) = 음수
z 의 첫번째 숫자는 1
3333333210 - (654321*1000) = 2679012210
2679012210 - (654321*1000) = 2024691210
2024691210 - (654321*1000) = 1370370210
1370370210 - (654321*1000) = 716049210
716049210 - (654321*1000) = 61728210
61728210 - (654321*1000) = 음수
z 의 두번째 숫자는 5
....

으로 계속해서 구하면 되지 않을까요?? -.-;;

랜덤여신의 이미지

글쓴이: 랜덤여신 / 작성시간: 토, 2004/06/12 - 1:45오후

vnl_bignum 이라는 것이 있습니다.

C++ 클래스이고, 큰 수의 덧셈/뺄셈/곱셈/나눗셈/나머지 연산을 할 수 있습니다.

다만, 저는 Visual C++ 6 에서 돌려 봤고, gcc 에서는 잘 돌아가는지는 모르겠네요. :?

첨부된 소스 파일의 확장자 cxx 는 cpp 로 바꿔서 사용하면 됩니다.

댓글 첨부 파일: 
첨부파일 크기
Package icon 0바이트

----
블로그 / 위키 / 리눅스 스크린샷 갤러리

댓글 달기

텍스트 포맷에 대한 자세한 정보

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.