Jump to content


Check out our Community Blogs

Register and join over 40,000 other developers!


Recent Status Updates

View All Updates

Photo
- - - - -

Check if an integer is a perfect square

pascal

  • Please log in to reply
7 replies to this topic

#1 sythanh14

sythanh14

    CC Lurker

  • New Member
  • Pip
  • 5 posts

Posted 15 December 2011 - 10:19 PM

Hey guys I will be very pleased if you help me to solve this problem. The problem is that I have to write a program whose code is written on Pascal to check if a positive integer less than 10^100 is a perfect square. I have already written its code but the result of the program is false. Will you help me, please!!
  • 0

#2 RhetoricalRuvim

RhetoricalRuvim

    JavaScript Programmer

  • Expert Member
  • PipPipPipPipPipPipPip
  • 1311 posts
  • Location:C:\Countries\US
  • Programming Language:C, Java, C++, PHP, Python, JavaScript

Posted 15 December 2011 - 10:48 PM

I don't know neither Pascal nor Delphi, but to think from the general programming perspective, I would say, have you tried taking the square root of the number and checking if the result is eligible for conversion to an integer without rounding?
  • 0

#3 Luthfi

Luthfi

    CC Leader

  • Expert Member
  • PipPipPipPipPipPipPip
  • 1320 posts
  • Programming Language:PHP, Delphi/Object Pascal, Pascal, Transact-SQL
  • Learning:C, Java, PHP

Posted 16 December 2011 - 02:32 AM

Yeah, basically you'd get the square root and see if it has fraction part or not. When it has, it's not perfect square.

To check whether a number has fraction part or not, you can subtract the number with its rounded value (i.e. its integer part) and see if the result is 0 or not. When not zero then it has fraction part.
  • 0

#4 sythanh14

sythanh14

    CC Lurker

  • New Member
  • Pip
  • 5 posts

Posted 16 December 2011 - 07:31 AM

Yeah it returns right for the number less than or equal to 4. But when I enter 5 it also says that this is a perfect square. You should also know that we can't get square root of a number greater than 10000000000000000000 in pascal. I have to use string in this program.
  • 0

#5 Luthfi

Luthfi

    CC Leader

  • Expert Member
  • PipPipPipPipPipPipPip
  • 1320 posts
  • Programming Language:PHP, Delphi/Object Pascal, Pascal, Transact-SQL
  • Learning:C, Java, PHP

Posted 16 December 2011 - 09:11 AM

If your code said 5 is perfect square, then your code definitely was wrong. Sqrt(5) returns 2.2360679775. I could not see why your code failed to detect the fraction part.

The number limitation is not only in Pascal, but also with any programming language. Since these kind of data type work in limited range only.
  • 0

#6 RhetoricalRuvim

RhetoricalRuvim

    JavaScript Programmer

  • Expert Member
  • PipPipPipPipPipPipPip
  • 1311 posts
  • Location:C:\Countries\US
  • Programming Language:C, Java, C++, PHP, Python, JavaScript

Posted 16 December 2011 - 11:27 AM

I don't really know of any particular or specific libraries or anything, but what about arbitrary precision arithmetic?


Also,
@sythanh: it would help if you don't mind posting that part of the code; you don't have to upload the whole program, just that line or two that does/do the checking.
  • 0

#7 sythanh14

sythanh14

    CC Lurker

  • New Member
  • Pip
  • 5 posts

Posted 17 December 2011 - 06:03 AM

The code is right here, see its length guy:
uses crt;
type bigNum = string; xau = array[1..1000000] of bigNum;
var t, so, temp: bigNum; pri: xau; kiemtra, i, dem, c, dai, dem1: longint;
    bool: boolean;
function cmp(a,b: bigNum): integer;
   begin
      while length(a)<length(b) do a:='0'+a;
      while length(b)<length(a) do b:='0'+b;
      if a>b then exit(1);
      if a<b then exit(-1);
      exit(0);
   end;
function add(a,b: bigNum): bigNum;
   var carry, i, sum: longint; c: string;
   begin
      carry:=0; c:='';
      while length(a)<length(b) do a:='0'+a;
      while length(b)<length(a) do b:='0'+b;
      for i:=length(a) downto 1 do
         begin
            sum:=ord(a[i])+ord(b[i])+carry-96;
            carry:=sum div 10;
            c:=chr(sum mod 10 + 48)+c;
         end;
         if carry>0 then c:='1'+c;
      add:=c;
   end;
function sub(a, b: bigNum): bigNum;
  var c: bigNum; s, borrow, i: longint;
  begin
    borrow:=0; c:='';
    while length(b)<length(a) do b:='0'+b;
    for i:=length(a) downto 1 do
       begin
          s:=ord(a[i])-ord(b[i])-borrow;
          if s<0 then
             begin
                s:=s+10;
                borrow:=1;
             end else borrow:=0;
             c:=chr(s+48)+c;
       end;
    while (length(c)>1) and (c[1]='0') do delete(c,1,1);
    sub:=c;
  end;
Function bigDiv2(a,b:bigNum):bigNum;
var c, hold:bigNum;
    kb:array[0..10] of bigNum;
    i,k:longint;
 begin
     kb[0]:='0';
     for i:=1 to 10 do
        kb[i]:=add(kb[i-1],b);
     hold:='';
     c:='';
     for i:=1 to length(a) do
       begin
          hold:=hold+a[i];
          k:=1;
          while cmp(hold,kb[k])<>-1 do
          inc(k);
          c:=chr(k-1+48);
          hold:=sub(hold,kb[k-1]);
       end;
     while (length(c)>1) and (c[1]='0') do delete(c,1,1);
     bigDiv2:=c;
 end;
function bigMod2(a, b: bigNum): bigNum;
  var hold: bigNum; kb: array[0..10] of bigNum; i, k: longint;
  begin
     kb[0]:='0';
     for i:=1 to 10 do kb[i]:=add(kb[i-1],b);
     hold:='';
     for i:=1 to length(a) do
        begin
           hold:=hold+a[i];
           k:=1;
           while cmp(hold, kb[k])<>-1 do
           inc(k);
           hold:=sub(hold, kb[k-1]);
        end;
     bigMod2:=hold;
  end;
procedure Eratosthene(n: bigNum; var prime: xau; dodai: longint);
var i, tmp, tmp1, k, e: longint; j: bigNum;
begin
    fillchar(prime,sizeof(prime),'0'); tmp1:=length(n) div 2 + 1;
    prime[1]:='2'; prime[2]:='3'; i:=2; j:='3'; dodai:=2;
    while (length(prime[i])<tmp1) and (i<=1000000) and (length(j)<tmp1) do
      begin
        j:=add(j,'1');
        tmp:=length(j) div 2 + 1; e:=0;
        for k:=1 to i do
           begin
              if (length(prime[k])<=tmp) and (bigMod2(j,prime[k])='0') then e:=1;
           end;
        if e=0 then begin inc(i); prime[i]:=j; inc(dodai); end;
      end;
end;
BEGIN
    CLRSCR;
    Writeln('   PROGRAM CHECKING IF AN INTEGER LESS THAN 10^100 ');
    Writeln('             IS A PERFECT SQUARE ');
    Write('   Enter the number needed to check: '); Readln(so);
    dem:=0;
    while (so[length(so)]='0') do begin inc(dem); delete(so,length(so),1); end;
    if odd(dem) then writeln('That number is not a perfect square') else
     if so='1' then writeln('That number is a perfect square') else
       begin
          delete(so, length(so)-dem, dem);
          kiemtra:=0; bool:=(so[length(so)]='2') or (so[length(so)]='3')
                or (so[length(so)]='7') or (so[length(so)]='8');
          if (so<>'1') and (kiemtra=0) then
             if bool then
                writeln('That number is not a perfect square') else
               begin
                 t:='1';
                 for c:=1 to (length(so) div 2 + 1) do t:=t+'0';
                 Eratosthene(t,pri,dai);
                 for c:=1 to dai do
                   begin
                     dem1:=0;
                     while bigMod2(so, pri[c])='0' do begin
                       so:=bigDiv2(so, pri[c]); inc(dem1);
                      end;
                     if odd(dem1) then begin kiemtra:=1; break;
                       end else kiemtra:=0;
                   end;
                 if kiemtra=1 then writeln('That number is not a perfect square')
                   else writeln('That number is a perfect square');
               end;
       end;
    readln
END.


---------- Post added at 09:03 PM ---------- Previous post was at 08:59 PM ----------

If your code said 5 is perfect square, then your code definitely was wrong. Sqrt(5) returns 2.2360679775. I could not see why your code failed to detect the fraction part.

The number limitation is not only in Pascal, but also with any programming language. Since these kind of data type work in limited range only.


I know that we can take the square root of an integer, but only in case that this number is not greater than 10^20. However, I have to write the code for processing the numbers greater than 10^20 to, so the code has to be in common. I don't wanna divide in so many cases. It can take a lot of time.
  • 0

#8 WingedPanther73

WingedPanther73

    A spammer's worst nightmare

  • Moderator
  • 17757 posts
  • Location:Upstate, South Carolina
  • Programming Language:C, C++, PL/SQL, Delphi/Object Pascal, Pascal, Transact-SQL, Others
  • Learning:Java, C#, PHP, JavaScript, Lisp, Fortran, Haskell, Others

Posted 17 December 2011 - 10:37 AM

You may want to implement a square root algorithm using the Babylonian method, or something similar.

Methods of computing square roots - Wikipedia, the free encyclopedia
  • 0

Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog

My MineCraft server site: http://banishedwings.enjin.com/






Also tagged with one or more of these keywords: pascal

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download