## 10023 - Square root

Moderator: Board moderators

Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Contact:

### Re: 10023 - Square Root

whats wrong with my code???
why WA????

Code: Select all

``````
#include<stdio.h>
#include<math.h>

int  main()

{

long double y;
int ncase;

scanf("%d",&ncase);

while(ncase>0)
{

scanf("\n\n%Lf",&y);

printf("%.0Lf",sqrtl(y));

if(ncase>1)
printf("\n\n");

ncase--;
}

return 0;

}
``````
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

### Re: 10023 - Square Root

Why do you think your code should get AC? long double != infinite precision arithmetic, go learn how floating-point numbers are really represented on a computer.

Ron
Learning poster
Posts: 55
Joined: Mon Jul 23, 2007 5:01 pm
Location: INDIA

### Re: 10023 - Square Root

hi mf sir,
could you please tell me the mistake in my above code.
I used BigInt. Just see my approach and tell me mistake ( if it is ).
Thanking You...!!!

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

### Re: 10023 - Square Root

When I tried to run your code on my computer, it doesn't work for small, two-digit inputs - the very first such test case runs ok, but for subsequent test cases it just prints "0". And also you're not reading the input properly - the test cases are separated by a blank line.

WingletE
New poster
Posts: 35
Joined: Sun Aug 13, 2006 1:34 pm
Location: Taipei, Taiwan
Contact:

### Runtime Error

My code runs okay on my computer and I really don't know why it got an RTE.
I've tried to enlarge the array of my BigInt to 2500, and checked that no divide-by-zero will possibly happen.
I think it's not the problem of array-index-out-of-bound because that should have caused a WA on my computer.
I'd be grateful if someone's willing to give me some suggestions or take a look at my code (tell me and I'll post it here or send it to you, because I think there's been too much code posted here).

noor_aub
New poster
Posts: 26
Joined: Sat Aug 22, 2009 12:16 pm

### Re: 10023 - Square Root

This code I get wrong answer. Why

Code: Select all

``````
``````
Last edited by noor_aub on Sun Aug 15, 2010 7:41 pm, edited 1 time in total.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

### Re: 10023 - Square Root

This code I get wrong answer. Why
Why not?

Bruno
New poster
Posts: 22
Joined: Thu Oct 01, 2009 9:03 pm

### Re: 10023 - Square Root

Following little joey algorithm (Pells equations, etc..) I got a very fast result! I tryed all the test cases from mukeshtiwari and all answers are equal! But I am getting WA

EDIT---

Got accpeted finally!
The problem was that in the last result I was printing a blank line too . Resuming, for EVERY number output you put a \n in the end, so the last number must have a \n too, between outputs you must print a \n (blank line)

mukeshtiwari
Learning poster
Posts: 63
Joined: Tue Mar 07, 2006 6:51 pm
Location: india

### Re: 10023 - Square Root

Edit; Posted in Java forum.Sorry for posting here.

mukeshtiwari
Learning poster
Posts: 63
Joined: Tue Mar 07, 2006 6:51 pm
Location: india

### Problem 10023 Square Root

Could some one please tell me why i am getting Run Time Error for this code.
Thank You

Code: Select all

``````/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/

//package uvaproblem_10023;
import java.io.*;
import java.math.BigInteger;

/**
*
* @author user
*/
public class Main {

/**
* @param args the command line arguments
*/
public static void main(String[] args) {
try
{
int n=Integer.parseInt(s_1);
boolean  f=false;
for(int i=0;i<n;i++)
{
if(f)System.out.println();
f=true;
BigInteger x=new BigInteger(s_2);
BigInteger lo=BigInteger.ZERO,hi=x,mid;
while(lo.compareTo(hi)<0)
{
BigInteger res=mid.pow(2);
else hi=mid;

}
//System.out.println(lo+" "+mid+" "+hi+" "+mid.pow(2));
System.out.println(mid);
}

}catch (NumberFormatException e){}
catch(IOException e){}
}

}

``````

mukeshtiwari
Learning poster
Posts: 63
Joined: Tue Mar 07, 2006 6:51 pm
Location: india

### Re: Problem 10023 Square Root

Today i tried again with try and catch block but no luck.I am still getting RTE. I guess this community not active as it was initially when i joined this site[around 2006-07].
Thank you

moron_venom
New poster
Posts: 1
Joined: Sat Mar 12, 2011 11:59 am

### Re: 10023 - Square Root

clould anyone help me to find the bug?

for all of test cases i tried, there are all correct

but the online judge always display runtime error ,but i can't find out where i straddle the boundary of array....

or maybe there's another mistake?

I use Square Root Extraction Method... i appreciate your help...

Code: Select all

``````
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int  cal[1100] ,rev_data[1100] ,guess[1100] ,divide_num[1100] ,answer[1100];
int rest[1100];
int rev_mul_test(int *guess ,int current_guess ,int *cal ,int * divide_num,int bottom ,int base ,int top);
int main(int argc, char *argv[])
{
int i,j  ,casenum ,digit_num ,d_num ,current_guess ,k;
char char_data;
int *tmp;
freopen("test.txt", "r", stdin);
freopen("dataout.txt", "w", stdout);
scanf("%d",&casenum);
for(i=0;i<casenum;i++){
digit_num = 0;
while(!isdigit(char_data)){
scanf("%c",&char_data);
}
rev_data[digit_num] = char_data -'0';
digit_num++;
while(scanf("%c",&char_data)!=EOF && isdigit(char_data)){
rev_data[digit_num] = char_data -'0';
digit_num++;
}
d_num = (digit_num+1)/2;
int top = 0 ,base=0 ,ans_num=0;
for(j=0;j<d_num;j++){
if(!j) guess[0] = 0;

if(digit_num%2 && !j){
divide_num[0] = rev_data[0];
top++;
}
else{
divide_num[top] = rev_data[top];
top++;
divide_num[top] = rev_data[top];
top++;
}

for(current_guess=0;current_guess<10;current_guess++){
guess[j+1] = current_guess;
if(!rev_mul_test(guess ,current_guess ,cal ,divide_num ,j+1 ,base ,top)){
break;
}
}
guess[j+1] = current_guess-1;
rev_mul_test(guess ,current_guess-1 ,cal ,divide_num ,j+1 ,base ,top);
ans_num++;
int pre_allzero=1;
for(k=base;k<top;k++){
/*   if(rest[k]) pre_allzero = 0;
if(pre_allzero && !rest[k]) base++;*/

divide_num[k] = rest[k];
}
int carry = 0,t;
for(k=j+1;k>=0;k--){
if(k==j+1){
t = (guess[k] + current_guess-1 +carry);
guess[k] = t % 10;
carry = t / 10;
}
else{
t = (guess[k] + carry);
guess[k] = t % 10;
carry = t / 10;
}
}
}
for(j=0;j<d_num;j++){
}
if(i!=casenum-1)
printf("\n\n");
else
printf("\n");

}

}
int rev_mul_test(int *guess ,int current_guess ,int *cal ,int * divide_num,int bottom ,int base ,int top){
int i,j,carry,t,effect_digit ,stop=0;
if(bottom==0 && top==0 && current_guess>3)return 0;
if(!guess[0]) stop=1;

for(i=base;i<top+1;i++) cal[i]=0;

effect_digit=0;
carry = 0;
for(i=bottom;i>=stop;i--){
t = guess[i] * current_guess + carry;
cal[top-bottom+i-1] = t % 10;
carry= t / 10;
if(current_guess)
effect_digit++;
}
if(carry>0 && top-bottom+i-1 < 0) return 0;
if(carry>0){
cal[top-bottom+i-1] = carry;
effect_digit++;
}
if(effect_digit > top-base)return 0;

carry = 0;
for (i=top-1;i>=base;i--){
rest[i] = divide_num[i] - cal[i] + carry;
if (rest[i] < 0) {
rest[i] = rest[i] + 10;
carry = -1;
}
else
carry = 0;
}
if(carry < 0)return 0;
else return 1;

}

``````

ojha
New poster
Posts: 7
Joined: Wed May 22, 2013 9:07 am

### Re: 10023 - Square Root

Is there any better logic than Newton's method ?? I'm getting Time Limit here:

Code: Select all

``````import java.math.BigInteger;
import java.util.Scanner;

public class Main {

public static void main(String[] args) {
Scanner scanf = new Scanner(System.in);
int time;
time = scanf.nextInt();
System.out.println("");

for(int i = 0; i<time; i++){
BigInteger input = scanf.nextBigInteger();
if(i > 0)
System.out.println("");
BigInteger previous = input;
BigInteger distance, post, Two = BigInteger.valueOf(2), Negative = BigInteger.valueOf(-1);
if(input.equals(BigInteger.ZERO)){
System.out.println("0");
continue;
}
while(true){
post = input.divide(previous);
post = post.divide(Two);
distance = post.subtract(previous);
if(distance.equals(BigInteger.ONE)){

System.out.println(previous);
break;
}
int d = distance.compareTo(BigInteger.ZERO);
if(d < 0)
distance = distance.multiply(Negative);
else if(distance.equals(BigInteger.ZERO)){

System.out.println(post);
break;
}
previous = post;
}
}

}

}
``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10023 - Square Root

Code: Select all

``````initialize temp to a guess of sqrt(Y)
while(1) {
X = (temp + (Y / temp)) / 2;
if(temp == X)
break;
temp = X;
}
``````
Check input and AC output for thousands of problems on uDebug!

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 10023 - Square Root

Is it possible to get acc using methods different from Pells and Newtons method?

I used square method which i learned at scholl and got TLE. I also got TLE using my own bigint + binary search

Code: Select all

``removed, after acc.. ``
I got acc with runtime 1.509. I found my bug. It was problem with reading number.

Then i changed base from 10 to 10000 + avoided all div and mod operations (by using some memory + precalc) + binary search for finding roots next digit (0..9) and some other optimizations and got acc with runtime 0.472.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman