Find a lowest number whose square ends in ...269696

[bplus]

Saw this at Liberty Basic and wow, tuffy for QB64

Code: QB64: [Select]

1. _TITLE "Find the number which squared ends in ...269696"
2. DIM n AS _INTEGER64
3. DO
4.     n = n + 1
5.     IF (n * n) MOD 269696 = 0 THEN PRINT n, n * n, (n * n) MOD 269696
6. LOOP UNTIL n = 30000
7.  
8. n = 25264
9. PRINT "The correct number is:"; n; " squared is"; n * n
10.  
11.  

hmm... looks like QB64 does not do MOD 269696, too big?

QB64 does 25264 * 25264 in E notation so can't look at RIGHT$(STR$(n*n), 6) either.

So is there a way to get the right answer n = 25264 shown above?

[STxAxTIC]

Just want to make sue you're excluding one possible branch here for the sake of the problem - i.e. what stops me from just using a large-number library I already have laying around? You can sure use right$ on that. Is it cheating?

[bplus]

Just want to make sue you're excluding one possible branch here for the sake of the problem - i.e. what stops me from just using a large-number library I already have laying around? You can sure use right$ on that. Is it cheating?

Well as a last resort, if we have to use a library, sure OK, back to string math...

But do we really have to? Surely there might be a clever way around? That's what I am hoping for.

[STxAxTIC]

Nevermind all that bplus, I got you. Watch:

Find the lowest number which squared ends in ...269696

So I write:

x^2 = A + 269696 ,

for some unknown x and A, and I also know that A = B * 10^6 for some unknown integer B. So:

x^2 = B * 10^6 + 269696

The task is NOT to scan over all x going way into the thousands, but scan over integers B, which only go into the 100s. Then look for x to be an integer as well. Run this code...

Code: QB64: [Select]

1. DIM x AS DOUBLE
2. FOR b = 1 TO 1000
3.     x = SQR(b * 10 ^ 6 + 269696)
4.     IF x = INT(x) THEN EXIT FOR
5. NEXT
6. PRINT b
7. PRINT x
8. PRINT x ^ 2

... get B = 638 and x = 25264.

And we're done.

25264^2 = 638269696

[bplus]

That's pretty sweet!

Now do you think we (you) have solved the problem for finding modulus of large numbers for QB64?

If so what is our new limit?

BTW Do you mind if I share this at Just Basic this is fantastic! (IMO)

[STxAxTIC]

Yikes, that MOD thing is a good question. My gut feeling is the above trick only skirts around needing MOD, but can't outright replace it in the generalized sense. I wonder if there's some trick one can do with division first to rescue MOD for really big numbers... Honestly I haven't thought about MOD much ever before. I'll remember this as something interesting... !!!

[bplus]

Well I am thinking maybe something with GCD.

 

[STxAxTIC]

Oh oops just saw your new edit - sure please do share that solution. While I just pulled it out of my hat, I don't claim any kind of ownership to the method. All credit goes to you instead for raising the question. (I've already got my prize ya know what I mean?)

[bplus]

Thanks, I am thinking "the prize" is the better question. ?

[STxAxTIC]

Suuuuuure, of course the prize is the better question *Pinocchio nose extends*

I was more-or-less referring to to the shiny green border around the response, haha... but egoism aside this does trigger me to wonder about the ins-and-outs of MOD - not so much *how* it works as is implemented in the compiler... I leave that to the engineering department. What I actually ponder now is: whenever you see MOD come up, just how avoidable is that situation in the first place? That is, if my calculations corner me into a computing MOD, especially a big one, can I "prove" there's always a way to avoid it? Maybe that question is the prize after all...?... Anyway. I still like the border too. XD

[bplus]

Oh man!

Code: QB64: [Select]

1. DIM a AS LONG
2. FOR a = 1 TO 30000
3.     IF a * a MOD 1000000 = 269696 THEN PRINT a: END
4. NEXT
5.  

Just shoot me. ;P

I posted at JB and am told I was just plain wrong! Yep QB64 modulus works just fine for high numbers what's not working so well is my brain.

Bill's is still a faster way, I don't think I am wrong on that account.

[STxAxTIC]

Say, does this problem have a name or other origin I can cite bplus? I'm looking to write it up and want to credit where ever the question started.

[bplus]

Say, does this problem have a name or other origin I can cite bplus? I'm looking to write it up and want to credit where ever the question started.

Here you go:
http://rosettacode.org/wiki/Babbage_problem

I scanned some of the codes and I think some other folks were onto the same idea as you (BBC Basic and IS Basic are examples.)

[STxAxTIC]

Thanks!

It only took me a few seconds to find "my" (which I knew couldn't be original) idea right in the applesoft basic code!

100 :
 110  REM  BABBAGE PROBLEM
 120 :
 130  DEF  FN ST(A) = N - INT (A) * INT (A)
 140 N = 269696
 150 N = N + 1000000
 160 R =  SQR (N)
 170  IF FN ST(R) <  > 0 AND N < 999999999 THEN GOTO 150           
 180  IF N > 999999999 THEN  GOTO 210                               
 190  PRINT "SMALLESt NUMBER WHOSE
      SQUARE ENDS IN"; CHR$ (13);
      "269696 IS ";R;", AND THE
      SQUARE IS"; CHR$ (13);N             
 200  END                               
 210  PRINT "THERE IS NO SOLUTION       
      FOR VALUES SMALLER"; CHR$(13);
      "THAN 999999999."     

[STxAxTIC]

... and it took 15 minutes too long to write it as sxript code with no loop, but a recursive function instead.

Code: QB64: [Select]

1. func(babbage,{(([x])*(10^6) + 269696)^.5}):
2. func(intc,{([x]=int([x]))}):
3.  
4. print_func(doit,{
5.   iff(intc(babbage([x])),{
6.     babbage([x])
7.   },{
8.     doit([x]+1)
9.   })
10. })(1)

I searched the Rosetta code page for "recur(sion)/(ive)" and found nothing, so I had to try.