[완료] BigInt 구현에 관한 질문..

senah의 이미지

음, 64비트 이상의 수치 자료형을 구현해야 할 필요가 있는데요.. long long은 C99에서는 표준이지만, 아직 C++에서는 표준으로 들어오지 않았고, Visual C++과 gcc에서 long long형에 대한 비트 조작이 조금 차이가 나는 부분이 있어서 그렇습니다. 그리고 64비트만 아니라, 128비트나 그 이상의 정밀도가 필요한 부분도 있어서 그렇습니다. (특히 부동소수점)

이미 구현되어 있는 BigInt들을 보면, 내부에 이진 자리수를 저장하는 배열을 가지고 있고, 이 배열에 대해서 비트 조작을 하게 됩니다. 그런데, 이렇게 되면 배열의 자료형을 아무리 작게 선언한다고 하더라도 1바이트의 크기를 가지고, 64비트 자료형을 구현한다고 하면 64바이트의 크기를 가지기 때문에, 좋은 구현은 아닌 것 같습니다.

다른 방법으로는 32비트 자료형 2개를 합쳐서 union으로 구현하는 방법을 생각해 볼 수 있는데, 기본 자료형의 크기를 벗어나는 수치값을, 나눠진 두 32비트 크기의 자료형에 정확하게 담는 방법이 잘 떠오르지 않네요.

BigInt와 같은 자료형을 구현해 보신 분 계신가요?

grassman의 이미지

쉽게 사용하려면 GNU MP Bignum Library를 쓰시면 될 듯 합니다.
속도도 빠르고 직접 구현하는 것 보다는 훨씬 안전합니다.

큰 수의 곱셈이나 나눗셈은 초등학교 때 배우던 방법과 동일하게 하면 됩니다.
다만 올림 수의 크기가 0~9가 아니라 0 ~ (2^32 - 1)이 되는게 다를 뿐입니다.
(32비트 자료형을 사용했을 때를 가정할 경우)

senah의 이미지

가져다 쓰는 것이라면 문제가 없지만, 구현을 해보려고 합니다. 소스포지에서 이런저런 라이브러리들을 살펴봤지만 마음에 드는게 없었는데, 한번 GMP를 살펴봐야 겠습니다. 소스를 한번 뜯어봐야 겠네요.

좋은 라이브러리 알려주신거 감사합니다. :)

gamdora의 이미지

이진수 배열이 아니라 65536진수 배열을 쓰면 되지 않을까요?

댓글 달기

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
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.