C++ or C# help please

Index > Main > C++ or C# help please

Author

Thread

magicSqr

Joined: 27 Aug 2011
Posts: 105

magicSqr 09 May 2013, 22:14

Hi,

I've been trying to convert the code below. I put it into Visual C# and VC++ so I could see what it was doing but it won't compile. If anyone could help translate into assembly (even BASIC would do) I'd be very grateful.

Code:

int putx, getx;

struct { int m,n; } MN_List[MANYMANY];

#define M_LIMIT 500
---------------------
Make_MN_List()
{ int m,n,s;

  putx = 0;
  getx = 0;

  MN_List[putx].m = 2;
  MN_List[putx].n = 1;

  ++putx;

  while (getx < putx)
  { m = MN_List[getx].m;
    n = MN_List[getx].n;
    ++getx;

    s = m + n;
    if (s < M_LIMIT)
    { Put_MN(s,m);
      Put_MN(s,n);
    }
  }
}

Put_MN(int m, int n)
{ int s;

  if ((n & 1) == 0)
  { MN_List[putx].m = m;
    MN_List[putx].n = n;
    ++putx;
  }
  else
  { s = m + n;
    if (s < M_LIMIT)
     {  MN_List[putx].m = s;
        MN_List[putx].n = m;
        ++putx;
        MN_List[putx].m = s;
        MN_List[putx].n = n;
        ++putx;
     }
  }
}

09 May 2013, 22:14

fredlllll

Joined: 17 Apr 2013
Posts: 56

fredlllll 09 May 2013, 22:52

should only work in c++. any error messages for us?
btw vc++ is the .net variant of c++. use an empty c++ project. and add a source file (.cpp)

09 May 2013, 22:52

magicSqr

Joined: 27 Aug 2011
Posts: 105

magicSqr 10 May 2013, 07:55

fredlllll wrote:

should only work in c++. any error messages for us?
btw vc++ is the .net variant of c++. use an empty c++ project. and add a source file (.cpp)

Hi fredlllll,

I know absolutely nothing about any flavour of C so am grateful for your help. The generic parts I'm ok with, i.e. s < M_LIMIT, ++getx. It's things like

MN_List[putx].m = 2;
m = MN_List[getx].m;

where I don't understand what is being put where.

Anyway, here's the code (with line numbers) followed by build error mesages
btw, I changed [MANYMANY] to [5000] as I'm assuming it means we need a lot of these data types, maybe I'm incorrect in this assumption

Code:

 1     int putx, getx;
 2
 3     struct { int m,n; } MN_List[5000];
 4
 5     #define M_LIMIT 500
 6     //---------------------
 7     Make_MN_List()
 8     { int m,n,s;
 9
10       putx = 0;
11       getx = 0;
12
13       MN_List[putx].m = 2;
14       MN_List[putx].n = 1;
15     
16       ++putx;
17     
18       while (getx < putx)
19       { m = MN_List[getx].m;
20         n = MN_List[getx].n;
21    ++getx;
22
23    s = m + n;
24    if (s < M_LIMIT)
25    { Put_MN(s,m);
26      Put_MN(s,n);
27         }
28       }
29     }
30
31     Put_MN(int m, int n)
32     { int s;
33     
34       if ((n & 1) == 0)
35       { MN_List[putx].m = m;
36         MN_List[putx].n = n;
37         ++putx;
38       }
39       else
40       { s = m + n;
41         if (s < M_LIMIT)
42          {  MN_List[putx].m = s;
43             MN_List[putx].n = m;
44             ++putx;
45             MN_List[putx].m = s;
46             MN_List[putx].n = n;
47             ++putx;
48          }
49       }
50     }

build output...

Code:

1>------ Build started: Project: fasm, Configuration: Debug Win32 ------
1>  fasm.cpp
1>e:\fasm.cpp(8): error C4430: missing type specifier - int assumed. Note: C++ does not support default-int
1>e:\fasm.cpp(25): error C3861: 'Put_MN': identifier not found
1>e:\fasm.cpp(26): error C3861: 'Put_MN': identifier not found
1>e:\fasm.cpp(29): warning C4508: 'Make_MN_List' : function should return a value; 'void' return type assumed
1>e:\fasm.cpp(32): error C4430: missing type specifier - int assumed. Note: C++ does not support default-int
1>e:\fasm.cpp(50): warning C4508: 'Put_MN' : function should return a value; 'void' return type assumed
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========

10 May 2013, 07:55

fredlllll

Joined: 17 Apr 2013
Posts: 56

fredlllll 10 May 2013, 08:03

MN_List[putx].m = 2;
m = MN_List[getx].m;

is accessing an array called MN_List. each element of this array has two sub elements called m and n. an array stars at 0 and ends at (length-1)

your methods dont have a specified returntype. they to be in format void Put_MN(...) for example.

i dont know where the loop will exist, so i cant tell what MANYMANY should be. isnt it defined somewhere in the got you got it from?

10 May 2013, 08:03

magicSqr

Joined: 27 Aug 2011
Posts: 105

magicSqr 10 May 2013, 08:18

fredlllll wrote:

...i dont know where the loop will exist, so i cant tell what MANYMANY should be. isnt it defined somewhere in the got you got it from?

Afraid not, this is the entire example code given.

afaik, it is meant to be (as you say) filling a 2-dimensional array with m, n values. These values have the following constraints ...

1. m > n > 0
2. m and n are coprime
3. m and n have opposite parity

on part 3, half of this is covered by part 2, (i.e. not both even) but, also, they cannot both be odd.

What I'm trying to understand from the code is where the condition for part 2 is being tested\satisfied as it doesn't appear to be testing GCD

output of MN_List would look like this...

2, 1
3, 2
4, 1
4, 3
5, 2
5, 4
6, 1
6, 5
etc.

I can simulate this in fasm, but need to check GCD of m and n

10 May 2013, 08:18

bitRAKE

Joined: 21 Jul 2003
Posts: 4073
Location: vpcmpistri

bitRAKE 10 May 2013, 09:59

Here is almost a direct conversion to asm:

Code:

M_LIMIT = 500
Make_MN_List:

; int m,n,s ; assume registers rbx,rbp,r15
    xor rsi,rsi ;getx = 0;
    xor rdi,rdi ;putx = 0;

    mov [MN_List.m+rdi*8],2;
    mov [MN_List.n+rdi*8],1;
    inc rdi ;++putx;
    jmp .while
.loop:
    mov ebx,[MN_List.m+rsi*8]
    mov ebp,[MN_List.n+rsi*8]
    inc rsi ;++getx;

    lea r15,[rbx+rbp] ;s = m + n;
    cmp r15,M_LIMIT ;if (s < M_LIMIT)
    jnc .skip

    mov rcx,r15
    mov rdx,rbx
    call Put_MN
    mov rcx,r15
    mov rdx,rbp
    call Put_MN
.skip:
.while:
    cmp rsi,rdi ; while (getx < putx)
    jc .loop
    retn


Put_MN: ;(int m, int n) {
;  int s; RAX
    test edx,1
    jnz .else

    mov [MN_List.m+rdi*8],ecx
    mov [MN_List.n+rdi*8],edx
    inc rdi
    retn
.else:
    lea rax,[rcx+rdx] ;s = m + n;
    cmp rax,M_LIMIT ;if (s < M_LIMIT)
    jnc .skip
    mov [MN_List.m+rdi*8],eax
    mov [MN_List.n+rdi*8],ecx
    inc rdi
    mov [MN_List.m+rdi*8],eax
    mov [MN_List.n+rdi*8],edx
    inc rdi
.skip:
    retn

Using registers for all the int's.

Note that Put_MN is always called twice, and it responds to parity of second parameter, storing either one or two structures, when even or odd, respectively.

; 2, 1 ; start resulting in 3,2 and 3,1 to be passed to Put_MN.
; 3, 2 ; Put_MN, 2 is even
; 4, 3 ; 4, 1 ; Put_MN, 1 is odd

...now run through with values (3,2), passing 5,3 and 5,2 to Put_MN. etc.

MN_List could be defined like:

Code:

MN_List:
  virtual
    .m dd ?
    .n dd ?
  end virtual
  rb 8*MANYMANY

(Code is all from my head - I didn't even run it through the compiler, or test. Should be close enough though.) Hope this helps a little.

_________________
¯\(°_o)/¯ “languages are not safe - uses can be” Bjarne Stroustrup

10 May 2013, 09:59

magicSqr

Joined: 27 Aug 2011
Posts: 105

magicSqr 10 May 2013, 11:57

Thanks bitRAKE,

I'll get a good look through it later but from a quick scan it looks very helpful.

btw, while you're on the scene, is bit-shifting and adding now defunct (due to proccessor speed) as a quicker method of multiply? I ran a test with 50,00 random qwords, looping 200 times and using the mul instruction loop was 60-100 times faster than shift\add

10 May 2013, 11:57

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20445
Location: In your JS exploiting you and your system

revolution 10 May 2013, 12:17

magicSqr wrote:

btw, while you're on the scene, is bit-shifting and adding now defunct (due to proccessor speed) as a quicker method of multiply?

No one can answer this definitively because there are too many variables involved, but in general using mul is probably going to be more efficient than any other method on most CPUs in use today. However, be aware that it is not guaranteed to be true in all cases.

10 May 2013, 12:17

magicSqr

Joined: 27 Aug 2011
Posts: 105

magicSqr 10 May 2013, 13:23

OK, thanks revolution. I'm working on a project that'll only be run on my poot, so mul it is Wink

10 May 2013, 13:23

bitRAKE

Joined: 21 Jul 2003
Posts: 4073
Location: vpcmpistri

bitRAKE 10 May 2013, 14:27

There is so much going on within the processor. Do a timing of the DIV/IDIV instruction with just power of two divisors for an unexpected result. It appears to me Intel is using an algorithm which is based on the number of bits set in the divisor -- that has been tweaked across all the different models.

Intel juggles the execution unit partitioning of instruction between different models as well. My development machine does okay with shift/adds, but they moved in the latest models to favor a different execution profile. This makes our job harder - timing code at several scales where needed.

Coding for size is so much easier - it's either fewer bytes, or not. Very Happy

_________________
¯\(°_o)/¯ “languages are not safe - uses can be” Bjarne Stroustrup

10 May 2013, 14:27

bitRAKE

Joined: 21 Jul 2003
Posts: 4073
Location: vpcmpistri

bitRAKE 10 May 2013, 16:22

magicSqr wrote:

What I'm trying to understand from the code is where the condition for part 2 is being tested\satisfied as it doesn't appear to be testing GCD.

If you are familiar with binary GCD, this algorithm is the reverse. The two parameters of Part_MN are never both even. Binary GCD subtracts in this case - here we do the opposite and add them. Smile

Forgot to answer this more explicitly.

_________________
¯\(°_o)/¯ “languages are not safe - uses can be” Bjarne Stroustrup

Last edited by bitRAKE on 10 May 2013, 16:33; edited 1 time in total

10 May 2013, 16:22

magicSqr

Joined: 27 Aug 2011
Posts: 105

magicSqr 10 May 2013, 16:32

bitRAKE wrote:

If you are familiar with binary GCD

Just coded my first attempt at binary GCD last week

bitRAKE wrote:

... Binary GCD subtracts in this case - here we do the opposite and add them.

Just what I was looking for then Very Happy

bitRAKE wrote:

Forgot to answer this more explicitly.

No probs, you've been a great help.

Many thanks

10 May 2013, 16:32

< Last Thread | Next Thread >

Forum Rules:

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum