-5
\$\begingroup\$

Given a natural number c as input, our task is finding the fastest way to calculate one -atleast- availabe integer solution (a,b) of pell equation c=a²-b².

Rules

Built-in functions and loopholes arent given any interest.

The program deals with integers (signed), the input is not supposed to abuse this range.

Output can be formatted in any form.

Your submission is scored by sum of milliseconds elapsed with these inputs:

6 17 489 1270453 5609331 92 3343 74721 3920.

Lowest time wins.

\$\endgroup\$
  • 4
    \$\begingroup\$ You might want to delete this...it's too simple for a fastest-code. \$\endgroup\$ – feersum Jun 26 '15 at 12:19
  • \$\begingroup\$ delete the tag or the whole question ? idont usually delete my challenges unless they are sufficiently unwelcome \$\endgroup\$ – Abr001am Jun 26 '15 at 12:20
  • \$\begingroup\$ Btw. I don't think that the input 6 has a solution. \$\endgroup\$ – Jakube Jun 26 '15 at 12:22
  • 6
    \$\begingroup\$ A benchmark which takes less than 10s has so much noise that it's useless. \$\endgroup\$ – Peter Taylor Jun 26 '15 at 13:55
  • 1
    \$\begingroup\$ Lowest time measured how? Are you going to time the submissions yourself? Otherwise, this is just a fastest computer challenge. \$\endgroup\$ – Dennis Jun 26 '15 at 14:35
5
\$\begingroup\$

nasm x64 i7 - 2 - 5 milliseconds

    extern  printf      
    section .bss

    section .data   
        fmt:           db "%i - %i", 10, 0      
        NumberToTestF  dq 5609331.0 ; put the number to test in floating
        NumberToTestI  dq 0         ; format, ie not 489, but 489.0 
        Counter        dq 0
        OutsideLoop    dq 0
        Divide1        dq 2
        Divide2        dq 1.7 
    section .text           

    global main     
    main:               
        push    rbp      
        mov rbp, rsp
        sub rsp, 32

        ; convert from float to int for faster cmp
        fld qword [NumberToTestF]   
        movq xmm0, qword [NumberToTestF]
        cvttsd2si rax, xmm0
        mov [NumberToTestI], rax

        ; Make 1st counter convert result to int
        fdiv qword [Divide2]
        fstp qword [OutsideLoop]
        movq xmm1, [OutsideLoop]
        cvttsd2si rax, xmm1
        mov [OutsideLoop], rax

        ; make counter
        mov r8, [Divide1]
        xor rdx, rdx
        mov rax, [NumberToTestI]
        idiv r8
        mov [Counter], rax

        ; initialize locals
        mov dword [rbp - 8], eax
        mov dword [rbp - 20], edi
        mov qword [rbp - 32], rsi
        jmp .l00p 

     .t0p:
        mov eax, [Counter]
        mov dword [rbp - 4], eax 
        jmp .b0tt0m  
     .inn3r:

        ; square & subtract each
        ; number 
        mov eax, dword [rbp - 8]
        mov edx, eax
        imul edx, dword [rbp - 8]
        mov eax, dword [rbp - 4]
        imul eax, dword [rbp - 4]
        mov ecx, edx
        sub ecx, eax
        mov eax, ecx

        ; final comparison
        ; if cmp == true print value
        ; & exit, if not keep looping
        cmp eax, [NumberToTestI]
        jnz .k33p0n
        mov eax, fmt
        mov edx, dword [rbp - 4]
        mov ecx, dword [rbp - 8]
        mov esi, ecx
        mov rdi, rax
        mov eax, 0
        call printf
        jmp .d0n3
    .k33p0n:        
        add dword [rbp - 4], 1
    .b0tt0m:
        mov eax, [OutsideLoop] 
        cmp dword [rbp-4], eax
        jle .inn3r 
        add dword [rbp - 8], 1  
    .l00p:  
        mov eax, [OutsideLoop]
        cmp dword [rbp-8], eax
        jle .t0p        
    .d0n3:
        mov eax,0       
        leave
        ret

Compile/link:
     nasm -f elf64 -o Break.o Break.asm
     gcc -o Break Break.o
\$\endgroup\$
  • \$\begingroup\$ code cant compile neither in remote compiler nor in my machine \$\endgroup\$ – Abr001am Jun 27 '15 at 12:03
  • 1
    \$\begingroup\$ Its for w/NASM version 2.09.10 . Explain your compiling errors. It works. \$\endgroup\$ – Pulga Jun 27 '15 at 14:25
  • \$\begingroup\$ gcc -o asm asm.o ------------------------ asm.o: file not recognized: File format not recognized ----------------------- collect2.exe: error: ld returned 1 exit status ----------------------- \$\endgroup\$ – Abr001am Jun 27 '15 at 16:49
  • \$\begingroup\$ U r doing something wrong. It works fine on both of my linux boxes & this online nasm assembler/linker/runner and you can view the output - dbgr.cc/l/nasm. Copy/paste everything starting w/extern ending w/ret then click the big run button \$\endgroup\$ – Pulga Jun 27 '15 at 17:47
  • \$\begingroup\$ still getting errors : hello_world.asm:48: warning: label alone on a line without a colon might be in error /nasmtrace/runit.sh: line 3: 17 Segmentation fault (core dumped) ./hello_world \$\endgroup\$ – Abr001am Jun 27 '15 at 17:56
1
\$\begingroup\$

Python, 130.0 Miliseconds

k=False
c = q
for i in range (int(c/2),int(c/1.7)):
    if k:
        break
    for x in range (int(c/2),int(c/1.7)):
        if i**2-x**2 == c: 
            print i,x
            k=True
            break
\$\endgroup\$
  • \$\begingroup\$ try to improve you answer please it takes atmost one loop \$\endgroup\$ – Abr001am Jun 27 '15 at 12:04
  • 2
    \$\begingroup\$ @Agawa001 can't see how, and this works pretty well. I guess I could speed it a little. \$\endgroup\$ – Tim Jun 27 '15 at 12:05
1
\$\begingroup\$

Axiom, 0.02 sec

v(c)==
  local m
  if c rem 2=0 then
        m:INT:=c/2
        if m rem 2~=0 then return [0,0]
        else return reverse sort  [(c/4)-1,(c/4)+1]
  reverse sort [1+(c-1)/2, (c-1)/2]

f()==for i in [6,17,489,1270453,92,3343,74721,3920] repeat output[i, v(i)]


(4) -> f()
   [6,[0,0]]
   [17,[8,9]]
   [489,[244,245]]
   [1270453,[635226,635227]]
   [92,[22,24]]
   [3343,[1671,1672]]
   [74721,[37360,37361]]
   [3920,[979,981]]
                                                               Type: Void
                                               Time: 0.02 (EV) = 0.02 sec

When integer equation b^2-a^2=c is not soluble in N+{0} return [0,0] one has to note there is no loop few remender and division so it is O(1)

-> v(6),v(17),v(489),v(1270453),v(92),v(3343),v(74721),v(3920)
 Compiling function v with type PositiveInteger -> List Fraction
    Integer

 [[0,0], [9,8], [245,244], [635227,635226], [24,22], [1672,1671],
  [37361,37360], [981,979]]

add some test

(13) -> r:=[6,17,489,1270453,92,3343,74721,3920,613352373758390083167447227749,5
82316870718762711394729885483949672964468220019,97658628223769028234818028188353
8549090329]

    (13)
   [6, 17, 489, 1270453, 92, 3343, 74721, 3920, 613352373758390083167447227749,
    582316870718762711394729885483949672964468220019,
    976586282237690282348180281883538549090329]
                                                   Type: List PositiveInteger
(14) -> a:=[v(i)  for i in r]

   (14)
   [[0,0], [9,8], [245,244], [635227,635226], [24,22], [1672,1671],
    [37361,37360], [981,979],
    [306676186879195041583723613875,306676186879195041583723613874],

     [291158435359381355697364942741974836482234110010,
      291158435359381355697364942741974836482234110009]
     ,

     [488293141118845141174090140941769274545165,
      488293141118845141174090140941769274545164]
     ]
                                         Type: List List Fraction Integer
(15) -> [a.i.1^2-a.i.2^2-r.i  for i in 1..#a]

   (15)  [- 6,0,0,0,0,0,0,0,0,0,0]
                                                  Type: List Fraction Integer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.